【题解】Trinity NTT,DP AGC021F

考虑设 $f(i,j)$ 表示 $i$ 行每行都有至少一格黑色的大小为 $i\times j$ 的表格的方案数。

最终的答案就是 $\sum {n\choose i}f(i,m)$ 。

考虑如何转移，每一次加入一列，并且加入若干行，最终的行数分成小于等于 $i$ 和大于 $i$ 两种。

考虑小于等于 $i$ 的情况，转移就是 $f(i,j)\rightarrow f(i,j+1)$ ，现在的问题就是转移系数，容易分成三种情况：

• 这一列没有黑色格子，方案数为 $1$ 。
• 这一列只有一个黑色格子，方案数为 $i$ 。
• 这一列有至少两个黑色格子，只需要考虑两个端点，中间的随意，两个端点的方案数为 ${i\choose 2}$ 。

接着考虑大于 $i$ 的情况，枚举 $k>i$ 表示新的行数。

注意加入行不是单纯的往后加，而是在中间插入。新加入的这些行的 $A_i$ 显然全部为 $j+1$ 。考虑新的一列的 $B_{j+1}$ ，可能是这些新加入行的第一行，也可能是原来的行中的一行，$C_{j+1}$ 同理。现在就是如何求 $B_{j+1}$ 和 $B_{j+1}$ 的方案数。

考虑求 $B_{j+1}-1,C_{j+1}+1$ 的方案数，也就是求第一个黑色格子的上面一个格子和最后一个格子的下面一个格子的方案数。那么新增加 $B,C$ 的两行，然后从 $k+2$ 行里面选出来 $k-i+2$ 行，选出来的 $k-i$ 行代表新增的行，$2$ 行代表 $B,C$ 。

为什么可以这样做？显然答案需要保证 $B_{j+1}$ 小于等于新加入的行中最上的一行，$C_{j+1}$ 必须保证大于等于新加入的行中最下的一行。

而唯一的难点就是如果直接求 $B,C$ 的话，因为新加入的行全为黑色，所以可能会算漏。

于是用将 $B$ 表示为原来 $B$ 上面的一行，$C$ 表示为原来 $C$ 下面的一行即可。但是允许 $(1,j+1)$ 或者 $(n,j+1)$ 是黑色，所以需要新增加两行。

对于这些 $B,C$ 相等的方案还是不一样的，因为里面新增的行，造成了 $A_i$ 的不一样。

(感觉有点啰嗦还是没讲明白= =，稍微感性理解一下吧 awa)

于是最终我们得到了转移：
$$
f(i,j)=\left(1+i+{i\choose 2}\right)f(i,j-1)+\sum_{k<i}{i+2\choose i-k+2}f(k,j-1)
$$
现在的状态数是 $O(nm)$ 的，转移复杂度为 $O(n)$ ，爆炸。

发现转移式左边可以直接计算，右边的话…：
$$
\sum_{k<i}\frac{(i+2)!}{(i-k+2)!k!}f(k,j-1)
$$
令 $g_1(i)=\frac{1}{(i+2)!}$ ，$g_2(i)=\frac{1}{i!}f(i,j-1)$ ，可以得到：
$$
(i+2)!\sum_{k<i}g_1(i-k)g_2(k)
$$
这就很显然了吧，直接 $\rm{NTT}$ 优化即可。

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=8e3+5;
const int M=2e2+5;
const int mod=998244353;
int n,m,f[N<<3],g1[N<<3],g2[N<<3],fac[N],inv[N],dp[N][M];

inline int mul(int x,int y) {return 1ll*x*y%mod;}
template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

namespace Poly {
    int filp[N<<3];
    inline int modpow(int x,int y,int res=1) {
        for(;y;y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x);
        return res;
    }
    inline void NTT(int*f,int limit,short inv) {
        for(int i=0;i<limit;++i) if(i<filp[i]) swap(f[i],f[filp[i]]);
        for(int p=2;p<=limit;p<<=1) {
            int len=p>>1,tmp=modpow(3,(mod-1)/p);
            for(int k=0;k<limit;k+=p) {
                int buf=1;
                for(int l=k;l<k+len;++l,buf=mul(buf,tmp)) {
                    int t=mul(f[l+len],buf);
                    f[l+len]=(f[l]-t+mod)%mod,f[l]=(f[l]+t)%mod;
                }
            }
        }
        if(inv==1) return;
        int sl=modpow(limit,mod-2);reverse(f+1,f+limit);
        for(int i=0;i<limit;++i) f[i]=1ll*f[i]*sl%mod;
    }
}using namespace Poly;

int limit=1,cnt=0;
inline int C(int n,int m) {return mul(fac[n],mul(inv[m],inv[n-m]));}
inline void solve(int j) {
    memset(g1,0,sizeof(g1));
    memset(g2,0,sizeof(g2));
    for(int i=1;i<=n;++i) g1[i]=inv[i+2];
    for(int i=0;i<=n;++i) g2[i]=mul(dp[i][j-1],inv[i]);
    for(int i=0;i<=n;++i) dp[i][j]=(dp[i][j]+mul(dp[i][j-1],(1+i+C(i,2))%mod))%mod;
    NTT(g1,limit,1),NTT(g2,limit,1);
    for(int i=0;i<limit;++i) f[i]=mul(g1[i],g2[i]);
    NTT(f,limit,-1);
    for(int i=1;i<=n;++i) dp[i][j]=(dp[i][j]+mul(f[i],fac[i+2]))%mod;
}

int main() {
    IN(n),IN(m),fac[0]=inv[0]=1;
    for(int i=1;i<=n+2;++i) fac[i]=mul(fac[i-1],i);
    for(int i=1;i<=n+2;++i) inv[i]=modpow(fac[i],mod-2);
    while(limit<((n+1)<<1)) limit<<=1,++cnt;
    for(int i=0;i<limit;++i) filp[i]=(filp[i>>1]>>1)|((i&1)<<(cnt-1));
    dp[0][0]=1;
    for(int j=1;j<=m;++j) solve(j);
    int ans=0;
    for(int i=0;i<=n;++i) ans=(ans+mul(C(n,i),dp[i][m]))%mod;
    printf("%d\n",(ans+mod)%mod);
    return 0;
}