UVa 11806




Link

https://vjudge.net/problem/UVA-11806

Type:

组合数学,排列预处理,容斥原理,减法取模公式

题意

给你一个M*N(M行N列)的棋盘和k个相同的石子,每个格子最多放一个石子,

问最上边,最左边,最下边,最右边都有石子的种数为多少?

题解

我们可以将问题转化为:

全集|S|-至少有一条边上没有棋子的种类个数.
并且我们可以发现,当四条边上都没有棋子时的种类个数为

C((m-2)*(n-2),k).

我们设A最左边没有石子,B为上边没有石子,C为右边没有石子,D为下边没有石子.

则(我们设~A为非A集合):

ans=|(~A)∩(~B)∩(~C)∩(~D)|

可以发现就是容斥原理
至于每个集合的计算,在图中就相当于少了一行或一列,
即:

C(row*column,k)

因为有: Sigma(i=1~4) C(4,i) = 2^4 = 16 种可能
即 可以用四位2进制表示

0000
0001
0010

我们设四位如下排列: (最左(减列),最上(减行),最右(减列),最下(减行))
等全部情况,在容斥中,其中1为奇数个时符号位是-,偶数是0

答案为全部的和.

Code

/*
Link: https://vjudge.net/problem/UVA-11806
Type: 组合数学,排列预处理,容斥原理,减法取模公式
题意: 给你一个M*N(M行N列)的棋盘和k个相同的石子,每个格子最多放一个石子,
问最上边,最左边,最下边,最右边都有石子的种数为多少?

题解:
我们可以将问题转化为:
全集|S|-至少有一条边上没有棋子的种类个数.
并且我们可以发现,当四条边上都没有棋子时的种类个数为
C((m-2)*(n-2),k).
我们设A最左边没有石子,B为上边没有石子,C为右边没有石子,
D为下边没有石子.
则(我们设~A为非A集合):
ans=|(~A)∩(~B)∩(~C)∩(~D)|
可以发现就是容斥原理
至于每个几何的计算,在图中就相当于少了一行或一列,
即:
C(row*column,k)
因为有: Sigma(i=1~4) C(4,i) = 2^4 = 16 种可能
即 可以用四位2进制表示
0000
0001
0010
我们设四位如下排列: (最左(减列),最上(减行),最右(减列),最下(减行))
等全部情况,在容斥中,其中1为奇数个时符号位是-,偶数是0
答案为全部的和.
*/
#include<bits/stdc++.h>
using namespace std;
const int mod=1e6+7;
int T;

const int MAXK=500;
int C[MAXK+10][MAXK+10];
void init(){
    memset(C,0,sizeof(C));
    C[0][0]=1;
    for(int i=0;i<=MAXK;++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 main(){
    init();
    cin>>T;
    for(int kase=1;kase<=T;++kase){
        int n,m,k;
        cin>>n>>m>>k;
        int sum=0;
        for(int i=0;i<16;++i){
            int nn=n,mm=m;
            int b=0;
            if(i&1){mm--;b++;}
            if(i&2){nn--;b++;}
            if(i&4){mm--;b++;}
            if(i&8){nn--;b++;}
            //奇数-偶数+
            if(b&1) sum=(sum+mod-C[nn*mm][k])%mod;
            else sum=(sum+C[nn*mm][k])%mod;
        }
        cout<<"Case "<<kase<<": "<<sum<<endl;
    }
    return 0;
}