题解 UVA11806 【Cheerleaders】

以下内容中C_{n}^{m}表示组合数。

考虑四角上四个点的情况:

1.四个角都不放人。

显然需要枚举最外圈(第一行、最后一行、第一列、最后一列的并集)除开四个角之外的放置方案。

设第一列、最后一列、第一行、最后一行中除开第一个位置和最后一个位置分别放置j_1,j_2,k_1,k_2个人,那么它们分别有:C_{n-2} ^{j_1},C_{n-2}^{j_2}, C_{m-2}^{k_1},C_{m-2}^{k_2}种放置方法。(需要保证1 \leq j_1,j_2,k_1,k_2 <kj_1+j_2+k_1+k_2 \leq k)

除开最外圈,里面还剩下left=k-(j_1+j_2+k_1+k_2)个人,需要把他们放置在中间共(m-2) (n-2) 个位置上。有C_{(m-2)  (n-2)}^{left} 种方法。

所以一共有( \sum C_{n-2}^{j_1} C_{n-2}^{j_2} C_{m-2}^{k_1} C_{m-2}^{k_2})  C_{(m-2)  (n-2)}^{left}种方案。

(也就是说要枚举j_1,j_2,k_1,k_2)

2.仅一个角放人。 那么又有四种情况:左上、左下、右上、右下。显然这四种是等价的,求一种之后乘以4即为答案。

为了方便讲述,假设选择了左上的那一个角。

那么第一行、第一列都不需要找了。为了使方案合法,我们需要一种方案,使得最后一行、最后一列都有人。

因为左下、右上、右下都不放人,所以最后一列n-2个位置中至少要选择一个人,最后一行m-2个位置中要选择至少一个人。

假设最后一列放j_1个人,最后一行放k_1个人,那么方案数为C_{n-2}^{j_1}  C_{m-2}^{k_1}.

除去左上角一个点、最后一整列、最后一整行,还剩下(m-1)  (n-1)-1个点可以放人,还剩下k-j_1-k_1-1个人需要放。

于是放这剩下的k-j_1-k_1-1个人就有C_{(m-1) (n-1)-1}^{k-j_1-k_1-1}种方法。

于是这种情况下有(\sum C_{n-2}^{j_1}  C_{m-2}^{k_1}) C_{(m-1)  (n-1)-1} ^ { k-j_1-k_1-1}种方法。

3.有且只有两个角放人。

假设这两个人不在同一对角线上

那么只有在n>2时才能在左上左下、右上右下放置。只有在m>2时才能在左上右上、左下右下放置。(否则若要满足情况,则不止要放2个角)。

假设n>2且在左上左下(或者右上右下)放置,那么只有最后一列(或者第一列)没有被覆盖了。我们需要在最后一列(或者第一列)的n-2个位置上选出至少一个人来参与。设选择j人,那么方案数为C_{n-2}^{j}

还剩下left=k-2-j个人,放置在nm-2-n个位置。

方案数为(\sum C_{n-2}^{j})  C_{n  m-2-n}^{left}
由于可以选左上左下或者右上右下,所以需要把这个玩意乘以2

同理,如果m>2且选择左上右上(或者左下右下),给最后一行(或者第一行)放置j个人,那么方案数共为:(\sum C_{m-2}^{j})  C_{n  m-2-m}^{left}。同样需要计数时乘以2

假设在同一对角线上:

除了四个角,每个位置都可以放置,方案数为C_{n m-4}^{k-2}。在对角线上有两种情况(左上右下,左下右上),所以这个数也要乘以2

4.有且只有三个角放人。

那么无论怎么放,都是满足条件的。
4个点中选出3个有C_{4}^{3}种方法,除开四角有C_{n  m - 4}^{k-3}种方法。

所以计数:C_{4}^{3}C_{nm-4}^{k-3}

5.所有角都放人。

那么所有角都放人有一种方法,除开这四个角共有C_{n  m -4}^{k-4}种方法,所以计数C_{nm-4}^{k-4}

当然要记得每步取模。

代码:

#include<cstdio>
#include<cstring>
// #define LOC

const long long mod=1000007;
long long C[505][505];
long long n,m,k;
long long ans;
long long T;
int kase;
void init(){
    C[0][0]=1;
    for(register int i=1;i<=500;++i){
        C[i][0]=1;
        for(register int j=1;j<=i;++j){
            C[i][j]=C[i-1][j-1]+C[i-1][j];
            C[i][j]%=mod;
            // printf("C[%d][%d]=%lld\n",i,j,C[i][j]);
        }
    }
}

void work(){
    scanf("%lld%lld%lld",&n,&m,&k);
    ans=0;
    if(m*n>=k){
        {//四个角都不放人
            for(register int j1=1;j1<=n-2;++j1){
                if(j1>=k)continue;
                for(register int j2=1;j2<=n-2;++j2){
                    if(j1+j2>=k)continue;
                    for(register int k1=1;k1<=m-2;++k1){
                        if(j1+j2+k1>=k)continue;
                        for(register int k2=1;k2<=m-2;++k2){
                            if(j1+j2+k1+k2>k)continue;
                            ans+=C[n-2][j1]*C[n-2][j2]%mod*C[m-2][k1]%mod*C[m-2][k2]%mod*C[(m-2)*(n-2)][k-(j1+j2+k1+k2)]%mod;
                            ans%=mod;
                        }
                    }
                }
            }
            ans%=mod;
        }

        {// 一个角上放人
            for(register int j1=1;j1<=n-2&&j1<k;++j1){
                for(register int k1=1;k1<=m-2;++k1){
                    if(j1+k1+1>k)continue;
                    ans+=C[n-2][j1]*C[m-2][k1]%mod*C[(m-1)*(n-1)-1][k-1-j1-k1]%mod*4%mod;
                    ans%=mod;
                }
            }
            ans%=mod;
        }

        {//左上左下或者右上右下放置
            for(register int j=1;j<=n-2&&j<=k-2;++j){
                ans+=C[n-2][j]*C[m*n-n-2][k-2-j]%mod*2%mod;
                ans%=mod;
            }
            ans%=mod;
        }

        {//左上右上或者左下右下放置
            for(register int j=1;j<=m-2&&j<=k-2;++j){
                ans+=C[m-2][j]*C[m*n-m-2][k-2-j]%mod*2%mod;
                ans%=mod;
            }
            ans%=mod;
        }


        if(k>=2){//对角线上放置
            ans+=2*C[m*n-4][k-2];
            ans%=mod;
        }

        if(k>=3){//三个角都放
            ans+=C[4][3]*C[m*n-4][k-3]%mod;
            ans%=mod;
        }

        if(k>=4){//四个角都放
            ans+=C[m*n-4][k-4];
            ans%=mod;
        }
    }
    printf("Case %d: %lld\n",++kase,ans);
}
int main(){
    scanf("%lld",&T);
    init();
    while(T--){
        work();
    }
    return 0;
}

留下评论

您的电子邮箱地址不会被公开。