旁边的dalao们，神们，都在做什么树套树平衡树LCT仙人掌模拟退火AC自动机……只有笔者这个蒟蒻弱弱的在写DP。这道Dp还是很有技术含量的。。
先分析一下题目，简单来说就是给一个矩阵，要求再里面放棋子，每行每列的棋子要<=2，问有多少种不同的放置方法。首先分析小数据，n，m均<=6，爆搜即可出解。然后那50%估计是有什么nm^3的做法，然而笔者太弱了没想出来。那么接着分析100%。
考虑到这个题就给了你行和列，所以我们以 行 为大方向考虑动归方程。思考，这么一来我们每行最多只能放两个棋子，那么如果我们以f[i][j][k]来表示到第i行已经有j列放了一个棋子，k列放了两个棋子的方法数量，那么DP完成后我们的答案就是sum（f[n][1...m][1...m]）。考虑如何转移：
首先，我们在下一行不放棋子，那么直接转移这一行的方案数就可以了。
其次，我们考虑在下一行放一个棋子，那么必须要分情况讨论：
①我们在当前已经有一个棋子的一列在放一个棋子，那么状态变为f[i+1][j-1][k+1]，而我们可以这么做的方案数就是已经放了j列一个棋子的j。
②我们从找一列一个棋子都没有的，放一个棋子，那么状态变为f[i+1][j+1][k]，我们能这么做的次数就是当前没有放旗子的列数（m-j-k）。
最后我们考虑在下一行放两个棋子，仍然需要分情况讨论，
①我们把这两个棋子全都放到已经有棋子的列，那么状态变为f[i+1][j-2][k+2],我们可行的不同的方案数就是从j个里面选出两个的数量也就是Cj2。
②我们放一个棋子在已经有棋子的一列，而另一个放在没有棋子的一列，那么状态变为f[i+1][j][k+1]，可行的不同方案数的个数是可以放有一个棋子的j和一个棋子都没有的(m-j-k)的乘积。
③我们把两个棋子都放在原来没有棋子的列上，那么状态变为f[i+1][j+2][k]，我们可行的方案数是。。
适当的%有益于身心，代码确实不长，但是确实是一道DP好题。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #define inf 5000001 8 #define re register 9 #define ll long long 10 #define min(a,b) a<b?a:b 11 #define maxn 5000007 12 #define mo 9999973 13 using namespace std; 14 ll f[201][201][201],n,k,m; 15 inline ll C(int x) 16 { 17 return x*(x-1)/2; 18 } 19 int main() 20 { 21 cin>>n>>m; 22 f[0][0][0]=1; 23 for(re int i=0;i<n;i++) 24 for(re int j=0;j<=m;j++) 25 for(re int l=0;l+j<=m;l++){ 26 if(f[i][j][k]){ 27 f[i+1][j][l]=(f[i+1][j][l]+f[i][j][l])%mo; 28 29 if(m-j-l>=1) f[i+1][j+1][l]=(f[i+1][j+1][l]+f[i][j][l]*(m-j-l))%mo; 30 if(j>=1) f[i+1][j-1][l+1]=(f[i+1][j-1][l+1]+f[i][j][l]*(j))%mo; 31 32 if(m-j-l>=2) f[i+1][j+2][l]=(f[i+1][j+2][l]+f[i][j][l]*C(m-j-l))%mo; 33 if(m-j-l>=1&&j>=1) f[i+1][j][l+1]=(f[i+1][j][l+1]+f[i][j][l]*(m-j-l)*j)%mo; 34 if(j>=2) f[i+1][j-2][l+2]=(f[i+1][j-2][l+2]+f[i][j][l]*C(j))%mo; 35 36 } 37 } 38 ll ans=0; 39 for(re int i=0;i<=m;i++) 40 for(re int j=0;j<=m;j++) 41 ans=(ans+f[n][i][j])%mo; 42 cout<<ans; 43 }