题意：

给一个n*m的棋盘，要求每一行列只能有不超过3个棋子，问方案数(棋子数任意)

\(n,m \le 100\)

题解：

这题唯一的脑洞之处就只有状态了

观察到每一行/列最多只能有2个，在这上面做手脚

设置\(f_{i,j,k}\)表示前i行完成，还有j列可以放2个，k列可以放1个

转移显然

过程：

很顺利，除了状态想了一会儿

代码：

const int N=110;const ll P=9999973;int n,m;ll f[N][N][N],C[N][N],ans;signed main() {    read(n); read(m);    for(int i=0;i<=100;i++) C[i][0]=1;    for(int i=1;i<=100;i++)        for(int j=1;j<=i;j++)            C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;    f[0][m][0]=1;    for(int i=0;i
    
     1) (f[i+1][j-2][k+2]+=val*C[j][2])%=P;                    if(k>1) (f[i+1][j][k-2]+=val*C[k][2])%=P;                }    for(int i=0;i<=m;i++)        for(int j=0;i+j<=m;j++)            (ans+=f[n][i][j])%=P;    printf("%lld\n",ans);    return 0;}
    

用时：15