题意翻译：
在 (n) 行 (m) 列的矩阵中放若干的点，使得每行每列的总点数小于或等于 (2) 。
填表法 DP :
考虑一行一行填表，对每一列状态进行分析
如「题意翻译」中所述，每一列只有三种合法状态，即放了 (1) 个， (2) 个或者 (0) 个点
这样就能写出状态：
(f(i,j,k,l)) 表示填了 (i) 行且有 (j) 列填有 (1) 个点， (k) 列填有 (2) 个点， (l) 列填有 (0) 个点时的方案数
显然，(ecause l=m-j-k) ， (l) 这一行可以舍去，空间复杂度达标
接下来就是状态转移方程了，因为每行只能放 (0,1,2) 个点，且每个点只能放在已经放 1 或 0 个点的列上，我们进行分类讨论
- 放 (0) 个点
[f(i,j,k) gets f(i,j,k)+f(i-1,j,k)
]
- 放 (1) 个点
- 放在已经放了一个点的列上
[f(i,j,k) gets f(i,j,k) + f(i-1,j+1,k-1) imes (j+1)
]
- 放在没有放任何点的列上
[f(i,j,k) gets f(i,j,k) + f(i-1,j-1,k) imes (m-(j-1)-k)
]
- 放 (2) 个点
- 一个点放在已经放一个点的列上，另一个点放在没有放任何点的列上
[f(i,j,k) gets f(i,j,k) + f(i-1,j,k-1) imes j imes (m-(j-1)-k)
]
- 两个点都放在已经放了一个点的列上
[f(i,j,k) gets f(i,j,k) + f(i-1,j+2,k-2) imes {j+2 choose 2}
]
- 两个点都放在没有放任何点的列上
[f(i,j,k) gets f(i,j,k) + f(i-1,j-2,k) imes {m-(j-2)-k choose 2}
]
所有情况讨论完毕
(operatorname{code})
#include<bits/stdc++.h>
using namespace std;
const int N = 120,P = 9999973;
int n,m;
long long f[N][N][N],ans;
int main() {
scanf("%d%d",&n,&m);
f[0][0][0] = 1;
for(int i=1;i<=n;++i)
for(int j=0;j<=m;++j)
for(int k=0;k<=m-j;++k) {
f[i][j][k] = f[i-1][j][k];
if(k) f[i][j][k] += f[i-1][j+1][k-1]*(j+1);
if(j) f[i][j][k] += f[i-1][j-1][k]*(m-j-k+1);
if(k) f[i][j][k] += f[i-1][j][k-1]*j*(m-j-k+1);
if(j>=2) f[i][j][k] += f[i-1][j-2][k]*(m-j-k+2)*(m-j-k+1)/2;
if(k>=2) f[i][j][k] += f[i-1][j+2][k-2]*(j+2)*(j+1)/2;
f[i][j][k] %= P;
}
for(int i=0;i<=m;++i)
for(int j=0;j<=m-i;++j) ans = (ans+f[n][i][j]) %P;
printf("%lld
",ans);
return 0;
}
tips: 若您是初小学生 (operatorname{C}_n^2) 可看成 (frac{n imes(n-1)}{2})
从 (n) 个点中选 (2) 个点，第一次有 (n) 个可能情况，第二次有 (n-1) 个可能情况，此时 ((a,b)) ((b,a)) 均被考虑，所以是 (frac{n imes(n-1)}{2})