n*m的矩形 k个人 第一行,最后一行,第一列,最后一列都至少站有一个人
小水题
正着做不好做,要反着想,那就容斥定理,ABCD四种情况分别是那四个行列分别没有人。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std; const int mod=;
const int K=; int c[][]; int main()
{
//freopen("a.in","r",stdin);
memset(c,,sizeof(c));
c[][]=;
for(int i=;i<=K;i++)
{
c[i][]=c[i][i]=;
for(int j=;j<i;j++)
c[i][j]=(c[i-][j]+c[i-][j-])%mod;
}
int T;
scanf("%d",&T);
for(int TT=;TT<=T;TT++)
{
int n,m,k,ans=;
scanf("%d%d%d",&n,&m,&k);
for(int s=;s<(<<);s++)
{
int nn=n,mm=m,sum=;
if(s&(<<)) nn--,sum++;
if(s&(<<)) mm--,sum++;
if(s&(<<)) nn--,sum++;
if(s&(<<)) mm--,sum++;
if(sum&) ans=(ans-c[nn*mm][k]+mod)%mod;
else ans=(ans+c[nn*mm][k])%mod;
}
printf("Case %d: %d\n",TT,ans);
}
return ;
}