题解 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 <k$ 且 $j_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;
}

题解 UVA11806 【Cheerleaders】

留下评论

取消回复