[JZOJ4870]涂色游戏

[JZOJ4870]涂色游戏

题目大意

给定一个 n×m $n\times m$的网格。你要给网格涂色，总共有 p $p$种颜色选择。要求满足任意相邻两列，都总共出现了至少q$q$种颜色。
计算方案数，答案对 998244353 $998244353$取模。

n≤100,m≤109,q≤p≤100 $n\le100,m\le10^9,q\le p\le 100$

---

题目分析

不要被神秘的模数吓到了。
条件只是限制了相邻两列，因此考虑单独考虑两列的合法方案数。
可以发现，如果在某一列之前的都是合法方案，我们在计算这一列时只不需要关注每个位置具体涂了什么颜色，只需要关心前一列填了多少种颜色，后一列填了多少种颜色，又有多少种颜色是两列都出现的。
设 fi,j $f_{i,j}$表示设当前考虑到第 i $i$列，当前列出现了j$j$种不同的颜色的方案数，且满足限制条件的方案数。
令 gi,j $g_{i,j}$表示前一列出现了 i $i$种不同的颜色，后一列出现了j$j$种不同的颜色，这两列满足限制条件的方案数。
那么我们有

fi,j=∑k=1nfi−1,kgk,j $$f_{i,j}=\sum_{k=1}^nf_{i-1,k}g_{k,j}$$
怎么求这个 gi,j $g_{i,j}$呢？枚举 k $k$表示两列共同出现的颜色个数，那么我们就有
gi,j=∑k=max(i+j−p,0)min(i,j,q)(ik)(p−ij−k)S(n,j)j! $$g_{i,j}=\sum_{k=\max(i+j-p,0)}^{\min(i,j,q)}{i\choose k}{p-i\choose j-k}S(n,j)j!$$
其中 S(n,j) $S(n,j)$是第二类 Stirling $\mathrm{Stirling}$数，表示将 n $n$个不同元素划分入j$j$集合的方案数。递推式 S(n,m)=S(n−1,m−1)+S(n−1,m)m $S(n,m)=S(n-1,m-1)+S(n-1,m)m$。
这样的计算是 O(n3+nm) $\mathrm O(n^3+nm)$的。
怎么优化呢？显然可以使用矩阵乘法优化 f $f$的计算，时间复杂度变为O(n3+n3log2m)$\mathrm O(n^3+n^3\log_2m)$。

---

代码实现

#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;const int P=998244353;
const int N=105;struct matrix
{int num[N][N];int r,c;
}f,one,zero;matrix operator*(matrix a,matrix b)
{matrix ret;memset(ret.num,0,sizeof ret.num);ret.r=a.r,ret.c=b.c;for (int i=0;i<ret.r;i++)for (int j=0;j<ret.c;j++)for (int k=0;k<a.c;k++)(ret.num[i][j]+=1ll*a.num[i][k]*b.num[k][j]%P)%=P;return ret;
}matrix operator^(matrix x,int y)
{matrix ret=zero;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;
}int C[N][N],h[N][N],fact[N];
int n,m,p,q,ans;void calc()
{fact[0]=1;for (int i=1;i<=p;i++) fact[i]=1ll*fact[i-1]*i%P;C[0][0]=1;for (int i=1;i<=p;i++){C[i][0]=1;for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;}h[0][0]=1;for (int i=1;i<=n;i++)for (int j=1;j<=i;j++)h[i][j]=(1ll*h[i-1][j]*j%P+h[i-1][j-1])%P;one.r=one.c=n;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)for (int k=max(i+j-p,0);k<=i&&k<=j&&k<=i+j-q;k++)(one.num[i-1][j-1]+=1ll*C[i][k]*C[p-i][j-k]%P*h[n][j]%P*fact[j]%P)%=P;zero.r=zero.c=n;for (int i=0;i<n;i++)zero.num[i][i]=1;f.r=1,f.c=n;for (int i=1;i<=n&&i<=p;i++) f.num[0][i-1]=1ll*C[p][i]*h[n][i]%P*fact[i]%P;f=f*(one^(m-1));ans=0;for (int i=1;i<=n;i++) (ans+=f.num[0][i-1])%=P;
}int main()
{freopen("color.in","r",stdin),freopen("color.out","w",stdout);scanf("%d%d%d%d",&n,&m,&p,&q);calc();printf("%d\n",ans);fclose(stdin),fclose(stdout);return 0;
}