刘汝佳《训练指南》里的一道例题。典型的容斥原理的应用。设C(M*N,K)为在M行，N列里放K个数的方案数。因为要求第一列，最后一列，第一行，，最后一行都有放置，显然答案为：
C(M*N,K)-(2*C(M*(N-1),K)+2*C((M-1)*N,K))+(4*C((M-1)*(N-1),K)+C(N*(M-2),K)+C((N-2)*M,K))-(2*C((N-2)*(M-1),K)+2*C((M-2)*(N-1),K))+C((M-2)*(N-2),K)
其实就是M*N行的解，减去其中一行或一列没有放置的解，加上两行，两列或一行和一列没放的情况…依次类推。开始我想直接将二项式系数C（）求解出来。但是…实在太大了，肯定会导致溢出。所以只能按照书上的方法写了，下面的代码基本和书上差不多。不过有一点需要注意，C[0][0]=1，果然这个边界条件没写，那么在处理类似M=2，N=2，K=0的时候就会出错。
先贴求二项式系数C()的代码，会产生溢出
long long C(int n,int k){if(n<k) return 0;long long ans=1;for(int i=1;i<=k;++i){ans=ans*(n-i+1)/i;//会溢出！}return ans%MOD;}
正确解答：
#include <iostream>#include <cstdio>#define MAX 400+5#define MAXK 500+5#define MOD 1000007using namespace std;int T,N,M,K,Case;int C[MAX][MAXK];int main(){cin>>T;C[0][0]=1;//注意边界！for(int i=1;i<MAX;i++){C[i][0]=C[i][i]=1;for(int j=1;j<i;++j){C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;}}while(T–){cin>>M>>N>>K;int ans=0;for(int S=0;S<16;++S){int b=0,r=M,c=N;if(S&1){b++,r–;}if(S&2){b++,r–;}if(S&4){b++,c–;}if(S&8){b++,c–;}if(b%2){ans=(ans+MOD-C[r*c][K])%MOD;}else{ans=(ans+C[r*c][K])%MOD;}}cout<<"Case "<<++Case<<": "<<ans<<endl;}return 0;}
没有行李，没有背包，不带电脑更不要手机，
