首先我们考虑设 \(dp_{i,j}\) 表示对于一个 \(i\times j\) 的网格,其每行都至少有一个黑格的合法的三元组 \((A,B,C)\) 的个数,那么对于原来的 \(n\times m\) 的网格,如果其存在黑格的行的集合不同,那么三元组 \((A,B,C)\) 肯定不同,因此我们可以直接枚举有多少行存在黑格来计算答案,即 \(ans=\sum\limits_{i=0}^n\dbinom{n}{i}dp_{i,m}\),因此我们只需求出 \(dp_{i,j}\) 即可求出答案。
接下来考虑怎样求出 \(dp_{i,j}\),首先边界条件肯定是 \(dp_{i,1}=1\),因为必须每格都染黑。接下来考虑转移,转移 \(dp_{i,j}\) 时,我们就枚举这个 \(i\times j\) 的矩阵前 \(j-1\) 列组成的子矩阵中,有多少行存在黑格,我们记这个数为 \(k\),那么可以这样从 \(dp_{k,j-1}\) 转移到 \(dp_{i,j}\):
故我们有 \(dp_{i,j}=dp_{i,j-1}(1+j+\dbinom{j}{2})+\sum\limits_{k=0}^{i-1}dp_{k,j-1}\dbinom{i+2}{i-k+2}\),这样暴力转移是 \(\mathcal O(n^2m)\) 的,无法通过,不过注意到后面一个 \(\sum\) 可以变形为 \(\sum\limits_{k=0}^{i-1}dp_{k,j-1}\dfrac{(i+2)!}{k!(i-k+2)!}=(i+2)!\sum\limits_{k=0}^{i-1}\dfrac{dp_{k,j-1}}{k!}\dfrac{1}{(i-k+2)!}\),这显然是一个卷积的形式,因此 NTT 优化即可,TC 即可降到 \(\mathcal O(nm\log n)\)。
const int MAXN=8000;
const int MAXM=200;
const int MAXP=1<<14;
const int MOD=998244353;
const int pr=3;
const int ipr=(MOD+1)/3;
int qpow(int x,int e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int n,m,dp[MAXN+5][MAXM+5],ans=0;
int fac[MAXN+5],ifac[MAXN+5];
void init_fac(int n){
for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int binom(int n,int k){return 1ll*fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;}
int rev[MAXP+5];
void NTT(vector<int> &a,int len,int type){
int lg=31-__builtin_clz(len);
for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
for(int i=0;i<len;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int i=2;i<=len;i<<=1){
int W=qpow((type<0)?ipr:pr,(MOD-1)/i);
for(int j=0;j<len;j+=i){
int w=1;
for(int k=0;k<(i>>1);k++,w=1ll*w*W%MOD){
int X=a[j+k],Y=1ll*a[(i>>1)+j+k]*w%MOD;
a[j+k]=(X+Y)%MOD;a[(i>>1)+j+k]=(X-Y+MOD)%MOD;
}
}
}
if(type==-1){
int iv=qpow(len,MOD-2);
for(int i=0;i<len;i++) a[i]=1ll*a[i]*iv%MOD;
}
}
vector<int> conv(vector<int> a,vector<int> b){
int LEN=1;while(LEN<a.size()+b.size()) LEN<<=1;
a.resize(LEN,0);b.resize(LEN,0);NTT(a,LEN,1);NTT(b,LEN,1);
for(int i=0;i<LEN;i++) a[i]=1ll*a[i]*b[i]%MOD;
NTT(a,LEN,-1);return a;
}
int main(){
scanf("%d%d",&n,&m);init_fac(n+2);
for(int i=0;i<=n;i++) dp[i][1]=1;
for(int j=2;j<=m;j++){
vector<int> a(n+1),b(n+1);
for(int i=1;i<=n;i++) a[i]=ifac[i+2];
for(int i=0;i<=n;i++) b[i]=1ll*ifac[i]*dp[i][j-1]%MOD;
a=conv(a,b);
for(int i=0;i<=n;i++){
dp[i][j]=1ll*(1+i+binom(i,2))*dp[i][j-1]%MOD;
dp[i][j]=(dp[i][j]+1ll*fac[i+2]*a[i])%MOD;
}
} for(int i=0;i<=n;i++) ans=(ans+1ll*binom(n,i)*dp[i][m])%MOD;
printf("%d\n",ans);
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章