[CSP-S模拟测试]:涂色游戏（DP+组合数+矩阵快速幂）

题目描述

小$A$和小$B$在做游戏。
他们找到了一个$n$行$m$列呈网格状的画板。小$A$拿出了$p$支不同颜色的画笔，开始在上面涂色。看到小$A$涂好的画板，小$B$觉得颜色太单调了，于是把画板擦干净，希望涂上使它看起来不单调的颜色（当然，每个格子里只能涂一种颜色）。小$B$想知道一共有多少种不单调的涂色方案。我们定义一个涂色方案是不单调的，当且仅当任意相邻两列都出现了至少$q$种颜色。

输入格式

一行四个整数$n,m,p,q$，意义如题中所述。

输出格式

一行一个整数，表示不单调的涂色方案数模$998244353$的值。

样例

样例输入：

2 3 3 3

样例输出：

162

数据范围与提示

对于$20\%$的数据：$n\times m\leqslant 15,q\leqslant p\leqslant 3$
对于另外$20\%$的数据：$n\leqslant 7,m\leqslant 100,p=q=2$
对于另外$30\%$的数据：$n\leqslant 100,m\leqslant 1,000,q\leqslant p\leqslant 100$
对于$100\%$的数据：$n\leqslant 100,m\leqslant {10}^9 ,q\leqslant p\leqslant 100$

题解

首先，明确题意，不能不涂（也是被这个我并没有看出来的条件坑死了……）

静观数据范围，显然是矩阵快速幂。

那么，我们现在思考如何构建转移矩阵。

先把矩阵搁在一边，考虑$DP$，设$f[i][j]$表示对于一列，选到了第$i$行的格子，恰好涂了$j$种颜色的方案数，直接给出式子：

$$f[i][j]=f[i-1][j-1]\times (p-(j-1))+f[i-1][j]\times j$$

前半部分的转移即为又选了一个新的，那么我就要在这么多的颜色中再选一个；后半部分相当于我又从原来的$j$中颜色中选了一种涂在了这里。

那么，我们在设$g[j]$表示对于一列，选了$j$种颜色的方案数，那么根据第二类斯特林数（类比将$n$个有区别的小球放进$m$个没有区别的盒子，每个盒子至少放一个小球），一列中涂上每种$j$元颜色集合的颜色的方案数就是$\frac{g[j]}{C_p^j}$。

那么，我们对于这一列用了$j$元集合，下一列要用$k$元集合，则方案数为：

$$\sum \limits_{x=\max(q,j,k)}^{\min(p,j+k)}C_j^{j+k-x}C_{p-i}^{x-j}$$

解释一下上式，考虑两个极端情况，$\alpha.j\cup k=\varnothing$，$\beta.j\subset k\ or\ k\subset j$，这也是上式的上下线；再来理解组合数，因为$j$和$k$会有交集，所以前一个组合数就是交集，而第二个就是交集以外的。

现在，我们令：

$$trans[j][k]=\frac{g[j]}{C_p^j}\sum \limits_{x=\max(q,j,k)}^{\min(p,j+k)}C_j^{j+k-x}C_{p-i}^{x-j}$$

那么，$dp[i][k]=dp[i-1][j]\times [j][k]$，$dp[1][j]=g[j]$。

这样我们就可以拿到$70$分了。

观察式子，可以用矩阵快速幂快速转移。

时间复杂度：$\Theta(n^3\log m)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

const int mod=998244353;

int n,m,p,q;

long long C[1001][1001],g[101][101];

long long wzc[101][101],ans[101][101],flag[101][101];

void matrix1()

{

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

		for(int j=1;j<=n;j++)

		{

			flag[i][j]=ans[i][j];

			ans[i][j]=0;

		}

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

		for(int j=1;j<=n;j++)

			for(int k=1;k<=n;k++)

				ans[i][j]=(ans[i][j]+flag[i][k]*wzc[k][j]%mod)%mod;

}

void matrix2()

{

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

		for(int j=1;j<=n;j++)

		{

			flag[i][j]=wzc[i][j];

			wzc[i][j]=0;

		}

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

		for(int j=1;j<=n;j++)

			for(int k=1;k<=n;k++)

				wzc[i][j]=(wzc[i][j]+flag[i][k]*flag[k][j]%mod)%mod;

}

void pre_work()

{

	g[0][0]=C[0][0]=1;

	for(int i=1;i<=100;i++)

	{

		C[i][0]=ans[i][i]=1;

		for(int j=1;j<=i;j++)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;

	}

}

int main()

{

	scanf("%d%d%d%d",&n,&m,&p,&q);

	pre_work();m--;

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

		for(int j=1;j<=n;j++)

			g[i][j]=j*(g[i-1][j]+g[i-1][j-1])%mod;

	for(int j=1;j<=p;j++)

		for(int k=1;k<=p;k++)

		{

			for(int x=max(max(q,j),k);x<=min(p,j+k);x++)

				wzc[j][k]=(wzc[j][k]+C[j][j+k-x]*C[p-j][x-j]%mod)%mod;

			wzc[j][k]=wzc[j][k]*g[n][k]%mod;

		}

	while(m)

	{

		if(m&1)matrix1();

		matrix2();

		m>>=1;

	}

	for(int i=1;i<=p;i++)

		for(int j=1;j<=p;j++)

			ans[0][0]=(ans[0][0]+ans[i][j]*C[p][i]%mod*g[n][i]%mod)%mod;

	printf("%lld",ans[0][0]);

	return 0;

}

rp++

巴特西