求k个石子放在n*m的矩阵里 并且第一行 最后一行 第一列 最后一列都要有石子
考虑反面 求出所有的 减去不满足的情况
容斥原理总共4个 集合A(第一行没有石子) B(最后行没有石子)C(第一列没有石子)D(最后一列没有石子)
减去1个集合的 加上2个集合的 减去3个集合的 加上4个集合的
#include <cstring>
#include <cstdio>
const int maxn = 510;
const int mod = 1000007;
int C[maxn][maxn];
int main()
{
C[0][0] = 1;
for(int i = 0; i <= 500; i++)
{
C[i][0] = C[i][i] = 1;
for(int j = 1; j < i; j++)
C[i][j] = (C[i-1][j] + C[i-1][j-1]) %mod;
}
int T;
int cas = 1;
scanf("%d", &T);
while(T--)
{
int n, m, k, sum = 0;
scanf("%d %d %d", &n, &m, &k);
for(int s = 0; s < 16; s++)
{
int b = 0, r = n, c = m;
if(s&1)
{
r--;
b++;
}
if(s&2)
{
r--;
b++;
}
if(s&4)
{
c--;
b++;
}
if(s&8)
{
c--;
b++;
}
if(b&1)
sum = ((sum - C[r*c][k]) % mod + mod) % mod;
else
sum = (sum + C[r*c][k]) % mod;
}
printf("Case %d: %d\n", cas++, sum);
}
return 0;
}