题目
有个(n*m)的黑白的方格，根据这个矩阵求得(A、B、C)三个数组
(A_i)表示第(i)行的第一个黑格的位置（如果没有就(m+1)）。
(B_i)表示第(i)列的第一个黑格的位置（如果没有就(n+1)）。
(C_i)表示第(j)列的最后一个黑格的位置（如果没有就(0)）。
求对于所有的涂色方案，不同的三元组((A,B,C))的数量。
(nleq 8000)
(mleq 200)
思考历程
看到这题后没有什么特别的思路。
分析了一些粗浅的性质，对正解（甚至拿部分分）没有什么帮助。
最终就是打了个暴力。
正解
设(f_{i,j})表示前(j)列中，强制(i)行有黑格，所得到的方案数。
考虑从(f_{i,j})转移到(f_{i+k,j+1})。
若(k=0)：
由于这(i)列都有黑格，所以在新增一列时，无论第(j+1)列怎么涂，(A)都不会再被更新。
所以只需要考虑(B)和(C)的影响。
很显然影响是(1+i+C_{i}^{2})
若(k>0)：
为了避免重复，新增的(k)行填的黑格子都在(j+1)列上。
原来的行的(A_i)不变，新增的行的(A_i=j+1)，所以对于(A)来说，方案数的不同在于新增(k)列的位置。将(k)列插入(i)列中，得出的不同的(A)乘上(C_{i+k}^k)种方案。
但是(B)、(C)就可能要难搞一些，因为原来的行在(j+1)列上有可能涂黑。
换个角度想一想，把(A)、(B)、(C)综合起来考虑。
分类讨论一下：
一、假设(B_{j+1})和(C_{j+1})都是新加的(k)行之一。
每一种新增(k)行插入原来的(i)行的方案，都会对应着有且仅有一个(B_{j+1})和(C_{j+1})的取值。
考虑上(A)的影响，每个方案的(A)都是不一样的，所以在这个情况下，每种插入的方案都对应着唯一的((A,B,C))。
方案数为(C_{i+k}^k)
二（三）、假设(B_{j+1})是原来的(i)行之一，(C_{j+1})是新加的(k)行之一（反之同理）：
可以这么理解：先把新增的(k)行插入原来的(i)行中，这时候对应着唯一的(A)，所以不用担心后面可能出现重复的情况。
插的第一个位置前面的行中任选一个作为(B_{j+1})
硬算的话，就先枚举第一个插入后的位置(x+1)（表示这个位置前面有(x)个原来的行），乘上(x)的贡献，然后将(k-1)行插入后面的(i+k-x-1)行中的贡献乘进去。列出个丑陋的式子，就是它的方案数。
通过组合数的定义来分析，这无非就是：在(i+k)个东西中，在位置(x+1)处选一个，然后它左边选(1)个，右边选(k-1)个。
这个东西不就是(i+k)个中选(k+1)个嘛！
方案数出来了：(C_{i+k}^{k+1})
四、假设(B_{j+1})和(C_{j+1})都是原来的(i)行之一
类似二的分析，得出方案数为(C_{i+k}^{k+2})
综合起来，贡献总共就是(C_{i+k+2}^{k+2})
把式子列出来，显然可以卷积。
NTT就完了。
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define L 16384
#define N 8010
#define M 210
#define ll long long
#define mo 998244353
ll qpow(ll x,int y=mo-2){
ll res=1;
for (;y;y>>=1,x=x*x%mo)
if (y&1)
res=res*x%mo;
return res;
}
int n,m;
ll fac[N],ifac[N];
ll f[N];
ll a[L],b[L],c[L];
int nN,lgn,re[L];
ll A[L],B[L],C[L];
inline void dft(ll A[],int flag){
for (int i=0;i<nN;++i)
if (i<re[i])
swap(A[i],A[re[i]]);
for (int i=1;i<nN;i<<=1){
ll wn=qpow(3,(mo-1)/(2*i));
if (flag==-1)
wn=qpow(wn);
for (int j=0;j<nN;j+=i<<1){
ll wnk=1;
for (int k=j;k<j+i;++k,wnk=wnk*wn%mo){
ll x=A[k],y=wnk*A[k+i]%mo;
A[k]=(x+y)%mo;
A[k+i]=(x-y+mo)%mo;
}
}
}
if (flag==-1){
ll inv=qpow(nN);
for (int i=0;i<nN;++i)
A[i]=A[i]*inv%mo;
}
}
inline void multi(ll c[],ll a[],ll b[]){
for (lgn=0,nN=1;nN<=2*n;nN<<=1,lgn++);
re[0]=0;
for (int i=1;i<nN;++i)
re[i]=re[i>>1]>>1|(i&1)<<lgn-1;
for (int i=0;i<nN;++i)
A[i]=a[i],B[i]=b[i];
dft(A,1),dft(B,1);
for (int i=0;i<nN;++i)
C[i]=A[i]*B[i]%mo;
dft(C,-1);
for (int i=0;i<nN;++i)
c[i]=C[i];
}
int main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d%d",&n,&m);
int most=max(n,m)+2;
fac[0]=1;
for (int i=1;i<=most;++i)
fac[i]=fac[i-1]*i%mo;
ifac[most]=qpow(fac[most]);
for (int i=most-1;i>=0;--i)
ifac[i]=ifac[i+1]*(i+1)%mo;
f[0]=1;
for (int j=1;j<=m;++j){
for (int i=0;i<=n;++i)
a[i]=f[i]*ifac[i]%mo;
b[0]=0;
for (int k=1;k<=n;++k)
b[k]=ifac[k+2];
multi(c,a,b);
for (ll i=0;i<=n;++i)
f[i]=(c[i]*fac[i+2]+f[i]*(1+i+(i*(i-1)>>1)%mo))%mo;
}
ll ans=0;
for (int i=0;i<=n;++i)
ans+=f[i]*fac[n]%mo*ifac[i]%mo*ifac[n-i]%mo;
printf("%lld
",ans%mo);
return 0;
}
总结
计数类的问题中，如果式子太复杂，就用定义的角度去分析它吧……