2015 JSOI冬令营训练彩色格子题解

解析

棋盘上黑白格染色。曼哈顿距离偶数：奇偶性相同。

枚举有几种颜色分到白格，组合数计算即可。

注意预处理，时间还是比较宽裕的。

为了不重复计数，考虑枚举严格用了i种颜色，我们再枚举分配j种给白集合。设白集合、黑集合大小分别为s1,s2，那么这种分配方案对答案的贡献为 $C^k_i$ $C^k_i$ $f_{s1,j}$ $f_{s2,i-j}$ $j!$ $(i-j)!$

$f_{i,j}$ 表示第二类斯特林数，表示将i个数分配到j个集合的方案数。

$f_{i,j}$ = $f_{i-1,j-1}$ + $f_{i-1,j}$ $\times j$

$f_{0,i}$ = $0^i$

这些东西都可以预处理。

注意边界要开好，不然n=1,m=1情况会错。

时间复杂度$ O(n^2 m^2+qK2) $。

代码

#include<bits/stdc++.h>

using namespace std;

const long long p=1000000007;

int T,n,m,k,s1,s2;

long long c[410][410],f[410][60],fact[410],ans;

bool mape[25][25];

int main(){

    scanf("%d",&T);

    c[0][0]=1;c[1][0]=c[1][1]=1;

    for(int i=2;i<=405;++i){

        for(int j=0;j<=i;++j){

            c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;

        }

    }

    f[0][0]=1;

    for(int i=1;i<=405;++i){

        for(int j=1;j<=50&&j<=i;++j){

            f[i][j]=(f[i-1][j]*j+f[i-1][j-1])%p;

        }

    }

    fact[0]=1;

    for(int i=1;i<=405;++i){

        fact[i]=(long long)i*fact[i-1]%p;

    }

    while(T--){

        scanf("%d %d %d",&n,&m,&k);

        s1=0,s2=0;

        for(int i=1;i<=n;++i){

            for(int j=1;j<=m;++j){

                mape[i][j]=(i&1)^(j&1);

                s1+=mape[i][j];

                s2+=1^mape[i][j];

            }

        }

        ans=0;

        for(int i=1;i<=k;++i){

            for(int j=0;j<=i;++j){

                (ans+=(((((c[k][i]%p*c[i][j])%p*f[s1][j])%p*f[s2][i-j])%p*fact[j])%p*fact[i-j])%p)%=p;

            }

        }

        printf("%lld\n",ans%p);

    }

    return 0;

}

巴特西

2015 JSOI冬令营训练彩色格子题解

最新文章

热门文章

巴特西

2015 JSOI冬令营训练 彩色格子 题解

最新文章

热门文章

2015 JSOI冬令营训练彩色格子题解