自己写的代码：
#include <iostream> #include <stdio.h> #include <string.h> /* 题意：相当于在一个m*n的矩形网格里放k个相同的石子，问有多少种方法？ 限制条件：每个格子最多放一个石子，所有石子都要用完，并且第一行、最后一行、第一列、最后一列都得有石子。 思路： 直接求的话会比较麻烦，反过来想： 设总方案数为S，A={第一行没有石子}，B={最后一行没有石子}，C={第一列没有石子}，D={最后一列没有石子} 利用容斥原理，先求|A并B并C并D|，然后再用|s|-|A并B并C并D|，即为答案。 而对于有r行，t列，摆放k个石子的方案数为C(r*t,k)。 */ using namespace std; const int maxn=25; const int mod=1000007; long long c[maxn*maxn][maxn*maxn]; int t,m,n,k; void init(){ memset(c,0,sizeof(c)); //先初始化为0，因为在计算容斥原理的时候，很有可能会出现C(i,j)(j>i)的情形，此时应该值为0 c[0][0]=1; for(int i=1;i<maxn*maxn;i++){ //求出组合数 c[i][0]=1; for(int j=1;j<i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; c[i][i]=1; } } int main() { long long ans,tmp; init(); scanf("%d",&t); for(int i=1;i<=t;i++){ ans=0; scanf("%d%d%d",&m,&n,&k); if(k>m*n||k<2) ans=0; else{ //先求|A并B并C并D|，由于只有四个元素，所以直接写出式子了 ans=(2*c[(m-1)*n][k]+2*c[m*(n-1)][k])%mod; tmp=((c[(m-2)*n][k]+4*c[(m-1)*(n-1)][k]%mod)%mod+c[(n-2)*m][k])%mod; ans=(ans-tmp+mod)%mod; ans=(ans+2*c[(m-2)*(n-1)][k])%mod; ans=(ans+2*c[(m-1)*(n-2)][k])%mod; ans=(ans+mod-c[(m-2)*(n-2)][k])%mod; ans=(c[m*n][k]-ans+mod)%mod; //最后再用所有总的方案数减去ans值，即为最后要求的答案 } printf("Case %d: %lld ",i,ans); } return 0; }
白书上的代码：
#include <iostream> #include <stdio.h> #include <string.h> /* 题意：相当于在一个m*n的矩形网格里放k个相同的石子，问有多少种方法？ 限制条件：每个格子最多放一个石子，所有石子都要用完，并且第一行、最后一行、第一列、最后一列都得有石子。 思路： 直接求的话会比较麻烦，反过来想： 设总方案数为S，A={第一行没有石子}，B={最后一行没有石子}，C={第一列没有石子}，D={最后一列没有石子} 利用容斥原理，先求|A并B并C并D|，然后再用|s|-|A并B并C并D|，即为答案。 而对于有r行，t列，摆放k个石子的方案数为C(r*t,k)。 */ using namespace std; const int maxn=25; const int mod=1000007; int C[maxn*maxn][maxn*maxn]; int t,m,n,k; void init(){ memset(C,0,sizeof(C)); //先初始化为0，因为在计算容斥原理的时候，很有可能会出现C(i,j)(j>i)的情形，此时应该值为0 C[0][0]=1; for(int i=1;i<maxn*maxn;i++){ //求出组合数 C[i][0]=1; for(int j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; C[i][i]=1; } } int main() { init(); scanf("%d",&t); for(int i=1;i<=t;i++){ int sum=0; scanf("%d%d%d",&m,&n,&k); //枚举所有16种搭配方式，s=0表明是总的方案数 //由于最后我们求的是补给的个数，所以在用容斥原理的时候稍作修改： //原本奇数个集合是加，改为减；偶数个集合是减，改为加 for(int s=0;s<16;s++){ int b=0,r=n,c=m; //b统计该方案数对应的集合的个数，r和c是可以放置的行列数 if(s&1){ b++; r--; } if(s&(1<<1)){ b++; r--; } if(s&(1<<2)){ b++; c--; } if(s&(1<<3)){ b++; c--; } if(b&1) sum=(sum+mod-C[r*c][k])%mod; //奇数个集合，做减法 else sum=(sum+C[r*c][k])%mod; //偶数个集合，做加法 } printf("Case %d: %d ",i,sum); } return 0; }