【问题描述】
小A 和小B 在做游戏。
他们找到了一个n 行m 列呈网格状的画板。小A 拿出了p 支不同颜色的画笔，开始在上面涂色。看到小A 涂好的画板，小B 觉得颜色太单调了，于是把画板擦干净，希望涂上使它看起来不单调的颜色（当然，每个格子里只能涂一种颜色）。小B 想知道一共有多少种不单调的涂色方案。我们定义一个涂色方案是不单调的，当且仅当任意相邻两列都出现了至少q 种颜色。
题解：
都能看出来这是道矩乘题。但是比较变态。
先不考虑矩阵，状态是f[ i ][ j ],指前i列已经填好，第i列共有j种不同颜色的方案数。
这里需要一个另外的g，用来算将j种颜色填入n个格子的方案数。
先来看一下g：（我用的是容斥）
for(int i=;i<=;i++)
{
g[i]=fast(i,n);//(快速幂)
for(int j=;j<i;j++)
{
g[i] = ((g[i] - g[j]*C[i][j]%MOD)%MOD+MOD)%MOD;
}
}
什么意思？
首先什么都不考虑，n个格子都有i种选择，得到i^n。
但是有个问题，就是原来让他有j种颜色，但是最终不够j。因此还要减掉g[ k ]*C[ j ][ k ]。
这样g就求完了。
然后就是状态转移方程了。
设前一列有k种颜色，当前列有j种颜色。
我分了几种情况：
1.k+j<q。这样无法转移……
2.k>=q或j>=q，这样当前列可以随便选，式子比较简单粗暴：
3.其他情况。这里需要枚举j中与k重合的有多少种。
最后转矩阵乘法。时间复杂度O(n^3*log m)。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MOD 998244353
#define ll long long
ll C[][],g[];
int n,m,p,q;
ll fast(ll x,int y)
{
ll ret = 1ll;
while(y)
{
if(y&)ret=ret*x%MOD;
x=x*x%MOD;
y>>=;
}
return ret;
}
struct mt
{
ll s[][];
}j0,j1;
mt operator * (mt a,mt b)
{
mt ret;
for(int i=;i<=p;i++)
{
for(int j=;j<=p;j++)
{
ret.s[i][j]=;
for(int k=;k<=p;k++)
{
(ret.s[i][j]+=a.s[i][k]*b.s[k][j]%MOD)%=MOD;
}
}
}
return ret;
}
void init()
{
C[][]=;
for(int i=;i<=;i++)
{
C[i][]=;
for(int j=;j<=i;j++)
{
C[i][j]=(C[i-][j-]+C[i-][j])%MOD;
}
}
for(int i=;i<=;i++)
{
g[i]=fast(i,n);
for(int j=;j<i;j++)
{
g[i] = ((g[i] - g[j]*C[i][j]%MOD)%MOD+MOD)%MOD;
}
}
for(int j=;j<=p;j++)
{
for(int k=;k<=p;k++)
{
if(j+k<q)
{
j0.s[j][k]=;
}else
{
if(k<q&&j<q)
{
for(int x=max(q,j)-k;x<=j&&x+k<=p;x++)
{
(j0.s[j][k]+=C[k][j-x]*C[p-k][x]%MOD*g[j]%MOD)%=MOD;
}
}else
{
j0.s[j][k]=C[p][j]*g[j]%MOD;
}
}
}
}
for(int i=;i<=p;i++)j1.s[i][]=g[i]*C[p][i]%MOD;
}
mt fastt(mt x,int y)
{
mt ret;
ret=x;
y--;
while(y)
{
if(y&)ret=ret*x;
x=x*x;
y>>=;
}
return ret;
}
int main()
{
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&p,&q);
init();
mt ans = fastt(j0,m-);
ans = ans*j1;
ll as = ;
for(int i=;i<=p;i++)
as = (as+ans.s[i][])%MOD;
printf("%lld\n",as);
return ;
}