嘟嘟嘟
啊我好菜啊，dp从来都做不出来……
这题我换了好几种状态但就是和题解不一样……
首先明确的一点是，每行每列最多有两个棋子，然后放置的方案数和顺序是无关的。所以没必要记录是怎么放的。
令dp[i][j][k]表示共(i)行，有(j)列放了1个棋子，有(k)列放了2个棋子（剩下的列就是没放棋子啦）的方案数。
然后枚举第(i)行放几个棋子，以及怎么放，转移方程看代码吧。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 105;
const int mod = 9999973;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m;
ll dp[maxn][maxn][maxn];
In void inc(ll& x, ll y)
{
x += y; if(x >= mod) x -= mod;
}
In ll C2(int n)
{
return 1LL * n * (n - 1) / 2;
}
int main()
{
n = read(), m = read();
dp[0][0][0] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= m; ++j)
for(int k = 0; k + j <= m; ++k)
{
inc(dp[i][j][k], dp[i - 1][j][k]); //不放
if(k) inc(dp[i][j][k], dp[i - 1][j + 1][k - 1] * (j + 1) % mod); //放1个在有1个棋子的列上
if(j) inc(dp[i][j][k], dp[i - 1][j - 1][k] * (m - j + 1 - k) % mod); //放1个在没有棋子的列上
if(j > 1) inc(dp[i][j][k], dp[i - 1][j - 2][k] * C2(m - j + 2 - k) % mod); //放2个在没有棋子的列上
if(k) inc(dp[i][j][k], dp[i - 1][j][k - 1] * j % mod * (m - j - k + 1) % mod); //放2个,分别在有0个和1个棋子的列上
if(k > 1) inc(dp[i][j][k], dp[i - 1][j + 2][k - 2] * C2(j + 2) % mod); //放2个在有1个棋子的列上
}
ll ans = 0;
for(int i = 0; i <= m; ++i)
for(int j = 0; i + j <= m; ++j) inc(ans, dp[n][i][j]);
write(ans), enter;
return 0;
}