一篇题解
# CQOI2011 放棋子
# 题目描述
在一个 行 列的棋盘里放一些彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列，有多少种方法？
# 分析
首先我们看到求方案读完题意，知道了相同颜色的棋子是可以在同一行和同一列任意排列的，但是这个不同颜色的棋子想要去求贡献会略有复杂，但是我们会发现要是计算方案数，它实际上是有一个顺序的，就比如你现在确定了 行 列，那么你当前的方案数是可以从 行 列和 行 列转移过来的，那么我们就很自然的会想到是不是可以用 来求。然后我们继续读题会进一步的发现方案数只跟当前确定了多少行和多少列以及现在考虑了多少颜色有关，那么我们就可以设 为当前已经考虑了 种颜色，并且已经确定了 行 列的方案数，我们这里对于具体是哪几行和哪几列并不关心，因为我们可以最后通过组合数去去重和求解，然后我们考虑如何去转移，我们肯定是枚举在考虑当前的颜色之前的方案数再乘上考虑当前颜色后的新增状态，为了方便计算，我们设 为用了 个颜色相同的棋子，确定了 行 列的方案数，那么状态转移方程即为
这个式子的意思就是之前确定了 行 列，那么我们剩下的 行 列就是通过 去确定的，然后由于我们的顺序是不确定的，那么我们可以从剩下的行和列中任意选择。
那么解决了 数组，接下来就来看 数组怎么求。
我们其实会发现正着去求 会很困难，但是我们求不合法的情况还是比较容易的，那么我们不妨容斥一下，拿总的方案数减去不合法的，那么式子就是
那么这个式子的意思就是所有的情况减去所有的之前的无法转移到当前状态的不合法状态的方案数，我们肯定是不能把自己减掉的，所以 和 是不能同时到达上限的。
然后这道题基本上就结束了，还有一个比较小的空间上的优化，但是也不怎么需要，就是我们会发现我们每个考虑的 实际上是不会依赖上一个状态的 数组的，因此，对于单独的一个状态，我们 数组的 这一维是固定的，那么我们可以直接对于每个颜色直接计算，不用再保留 数组的 这一维。
#include <cstring> | |
#include <iostream> | |
#include <algorithm> | |
namespace read_write | |
{ | |
template <typename T> | |
inline void read(T &x) | |
{ | |
x = 0; | |
T f = 1; | |
char ch = getchar(); | |
while (ch > '9' || ch < '0') | |
{ | |
if (ch == '-') | |
f = -1; | |
ch = getchar(); | |
} | |
while (ch >= '0' && ch <= '9') | |
x = x * 10 + ch - '0', ch = getchar(); | |
x *= f; | |
return; | |
} | |
template <typename T, typename... Args> | |
inline void read(T &first, Args &...args) | |
{ | |
read(first); | |
read(args...); | |
} | |
template <typename T> | |
inline void write(T x) | |
{ | |
if (x < 0) | |
{ | |
x = -x; | |
putchar('-'); | |
} | |
if (x > 9) | |
write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
template <typename T> | |
T max(T x, T y) | |
{ | |
return x > y ? x : y; | |
} | |
template <typename T> | |
T min(T x, T y) | |
{ | |
return x > y ? y : x; | |
} | |
template <typename T> | |
void swap(T &a, T &b) | |
{ | |
T tem = b; | |
b = a; | |
a = tem; | |
} | |
} | |
namespace Solve | |
{ | |
using namespace read_write; | |
#define int long long | |
const int N = 960, mod = 1e9 + 9; | |
int n, m, c, ans; | |
int C[N][N], cnt[N]; | |
int f[N][N][12], g[N][N]; | |
void init() | |
{ | |
for(int i = 0 ; i < N ; ++ i) | |
{ | |
C[i][0] = 1; | |
for(int j = 1 ; j <= i ; ++ j) | |
C[i][j] = C[i - 1][j] + C[i - 1][j - 1] % mod; | |
} | |
} | |
void calc_g(int &x, int l, int r) | |
{ | |
for(int i = 1 ; i <= l ; ++ i) | |
for(int j = 1 ; j <= r ; ++ j) | |
if(i < l || j < r) | |
x = (x + g[i][j] * C[l][i] % mod * C[r][j] % mod + mod) % mod; | |
} | |
int calc_f(int l, int r, int k) | |
{ | |
int res = 0; | |
for(int i = 0 ; i < l ; ++ i) | |
for(int j = 0 ; j < r ; ++ j) | |
if((l - i) * (r - j) >= cnt[k]) | |
res = (res + f[i][j][k - 1] % mod * g[l - i][r - j] % mod * C[n - i][l - i] % mod * C[m - j][r - j] % mod + mod) % mod; | |
return res; | |
} | |
void solve() | |
{ | |
read(n, m, c); | |
init(); | |
f[0][0][0] = 1; | |
for(int id = 1 ; id <= c ; ++ id) | |
{ | |
read(cnt[id]); | |
memset(g, 0, sizeof(g)); | |
for(int i = 1 ; i <= n ; ++ i) | |
{ | |
for(int j = 1 ; j <= m ; ++ j) | |
{ | |
if(i * j >= cnt[id]) | |
{ | |
int sum = 0; | |
calc_g(sum, i, j); | |
g[i][j] = (C[i * j][cnt[id]] - sum + mod) % mod; | |
} | |
} | |
} | |
for(int i = 1 ; i <= n ; ++ i) | |
for(int j = 1 ; j <= m ; ++ j) | |
f[i][j][id] = calc_f(i, j, id) % mod; | |
} | |
for(int i = 1 ; i <= n ; ++ i) | |
for(int j = 1 ; j <= m ; ++ j) | |
ans = (ans + f[i][j][c] % mod + mod ) % mod; | |
write(ans); | |
} | |
} | |
signed main() | |
{ | |
Solve :: solve(); | |
return 0; | |
} |
