啊我好菜啊，dp从来都做不出来……
这题我换了好几种状态但就是和题解不一样……
首先明确的一点是，每行每列最多有两个棋子，然后放置的方案数和顺序是无关的。所以没必要记录是怎么放的。
令dp[i][j][k]表示共
\(i\)行，有
\(j\)列放了1个棋子，有
\(k\)列放了2个棋子（剩下的列就是没放棋子啦）的方案数。
然后枚举第
\(i\)行放几个棋子，以及怎么放，转移方程看代码吧。
#include #include #include #include #include #include #include #include #include #include using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define In inlinetypedef 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;}