Cheerleaders UVA – 11806

Cheerleaders – UVA 11806 – Virtual Judge

题目大意：有一个n*m的网格，要把其中k个格子涂黑，且满足最上、下一行、最左、右一列分别至少有一格黑，问方案数有多少

2<=m,n<=50；k<=500

思路：因为合法的方案数不好考虑，所以考察不合法的方案数，我们设第一行没有黑格为A，第一列没有黑格为B，最后一行没有黑格为C，最后一列没有黑格为D，根据容斥原理有：非法方案数=-A-B-C-D+AB+AC+AD+BC+BD+CD-ABC-ABD-ACD-BCD+ABCD，这些都可以用组合数算，就是从除了选中行/列以外的格子里选k个，例如A=C[n*m-m][k]，AB=C[n*m-n-m+1][k]。

因为题目中的模数不是质数，所以不能用常规打表阶乘逆元的方法算，因为数据范围很小，所以可以用递推转移的方法打表，首先初始化C[i][0]和C[i][i]都是1，对于1到i-1，有c[i][j]=C[i-1]j]+C[i-1][j-1]，我们将15个几何都算出来求和即可。

#include//#includeusing namespace std;typedef long long ll;const int N = 1e6 + 5;const ll MOD = 1e6 + 7;ll n;ll inv[N], fac[N];ll C[405][405];void calC(){//打表预处理组合数C[0][0] = 1;for (int i = 1; i <= 400; i++){C[i][0] = C[i][i] = 1;//边界都是1for (int j = 1; j > n >> m >> k;ll ans = C[n * m][k];//总方案数ans = (ans - C[n * m - n][k] + MOD) % MOD;//Aans = (ans - C[n * m - n][k] + MOD) % MOD;//Bans = (ans - C[n * m - m][k] + MOD) % MOD;//Cans = (ans - C[n * m - m][k] + MOD) % MOD;//Dans = (ans + C[n * m - n - m + 1][k]) % MOD;//ABans = (ans + C[n * m - n - m + 1][k]) % MOD;//ADans = (ans + C[n * m - n - n][k]) % MOD;//ACans = (ans + C[n * m - m - m][k]) % MOD;//BDans = (ans + C[n * m - m - n + 1][k]) % MOD;//BCans = (ans + C[n * m - n - m + 1][k]) % MOD;//CDans = (ans - C[n * m - 2 * n - m + 2][k] + MOD) % MOD;//ABCans = (ans - C[n * m - 2 * n - m + 2][k] + MOD) % MOD;//ACDans = (ans - C[n * m - 2 * m - n + 2][k] + MOD) % MOD;//BCDans = (ans - C[n * m - 2 * m - n + 2][k] + MOD) % MOD;//ABDans = (ans + C[n * m - 2 * m - 2 * n + 4][k]) % MOD;//ABCDcout << "Case " << t << ": " << ans % MOD <> t;calC();int cnt = 0;while (t--){cnt++;solve(cnt); }return 0;}