menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[思维+第二类斯特林数]BZOJ5413【color】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

用 $K$ 种颜色对 $n\times m$ 的网格进行染色,需要保证无论怎么样纵切将棋盘分为左右两个部分, 两个部分的颜色种类数都必须相等,求方案数。

解题报告

在NOIP前,这道题被法老当做NOIP题出进了模拟赛……

考虑第一列有 $a$ 种颜色,那么 $[2,m]$ 列也有 $a$ 种颜色,再考虑前两列有 $x(x\ge a)$ 种颜色,那么 $[3,m]$ 列也有 $x(x\le a)$ 种颜色,所以 $x=a$ ,以此类推所有格子只有 $a$ 种颜色,反过来考虑同理。

因此我们可以枚举 $a$ 表示第一列和第 $n$ 列有 $a$ 种颜色,那么中间 $m-2$ 列只能使用第一列和第 $n$ 列颜色的交集,假设有 $b$ 种颜色,则方案数为:

$$ \sum_{a=1}^{min\{n,K\}}\sum_{b=0}^{a}{K\choose a}{K-a\choose a-b}{a\choose b}b^{n(m-2)}[S(n,a)a!]^2 $$

前面一堆就表示选出 $a$ 种颜色,$b$ 种交集,中间用 $b$ 种颜色的方案数,后面那个 $S(n,a)$ 表示第二类斯特林数,$[S(n,a)a!]^2$ 表示第一列和第 $n$ 列涂上 $a$ 种颜色的方案数。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000,maxk=1000000,MOD=1000000007;

int te,n,m,K,fac[maxk+5],INV[maxk+5],S[maxn+5][maxn+5],ans;

inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
#define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    INV[0]=INV[1]=1;for (int i=2;i<=maxk;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=maxk;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD;
    S[0][0]=1;for (int i=1;i<=maxn;i++) for (int j=1;j<=i;j++) S[i][j]=(S[i-1][j-1]+(LL)S[i-1][j]*j%MOD)%MOD;
    for (int i=0;i<=maxn;i++) for (int j=1;j<=i;j++) S[i][j]=Pow((LL)S[i][j]*fac[j]%MOD,2);
    for (scanf("%d",&te);te;te--){
        scanf("%d%d%d",&n,&m,&K);ans=0;if (m==1) {printf("%d\n",Pow(K,n));continue;}
        for (int i=1;i<=n&&i<=K;i++)
            for (int j=0;j<=i;j++)
                ans=(ans+(LL)C(K,i)*C(K-i,i-j)%MOD*C(i,j)%MOD*Pow(j,n*(m-2))%MOD*S[n][i]%MOD)%MOD;
        printf("%d\n",ans);
    }return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up