题目大意
?? 在一个 \(n\)行 \(m\)列的棋盘上 (\(1 \leq n,m \leq 100\)), 要求每行每列最多能放 \(2\) 个棋子, 求方案数 $\bmod 9999973
$.
?
题解
?? 比较有意思的 dp.
?? 我们可以设 \(dp[I][i][j][k]\)表示从第 \(1\)到第 \(I\)行, 有 \(i\)列只有 \(1\)个棋子, 有 \(j\)列只有 \(2\)个棋子, 有 \(k\)列只有 \(0\)个棋子的总方案数.
?? 显然 \(k\)可以由 \(m\)和 \(i\),\(j\)得到, 可以去掉这一维. 当然也可以用滚动数组优化.
?? 因为每行每列都最多能放 \(2\)个棋子所以 dp 的状态转移方程只有最多 \(5\)种情况, 分别枚举即可, 具体看下面的代码应该都能理解.
- #include <iostream>
- #define MAX_N 100
- #define MAX_M 100
- #define MOD 9999973
- using namespace std;
- int n, m;
- long long dp[MAX_N | 1][MAX_N | 1][2];
- // i: 有 1 个棋子的列
- // j: 有 2 个棋子的列
- int ans;
- inline int C(int x)
- {
- return x * (x + 1)>> 1;
- }
- int main()
- {
- cin>> n>> m;
- dp[0][0][1] = 1;
- dp[1][0][1] = m;
- dp[2][0][1] = C(m - 1);
- for(register int k = 2; k <= n; ++k)
- {
- for(register int i = 0; i <= m; ++i)
- {
- for(register int j = 0; i + j <= m; ++j)
- {
- dp[i][j][k & 1] = dp[i][j][k + 1 & 1];
- if(i) dp[i][j][k & 1] = (dp[i][j][k & 1] + dp[i - 1][j][k + 1 & 1] * (m - i - j + 1)) % MOD;
- if(i> 1) dp[i][j][k & 1] = (dp[i][j][k & 1] + dp[i - 2][j][k + 1 & 1] * C(m - i - j + 1)) % MOD;
- if(j) dp[i][j][k & 1] = (dp[i][j][k & 1] + dp[i + 1][j - 1][k + 1 & 1] * (i + 1)) % MOD;
- if(j> 1) dp[i][j][k & 1] = (dp[i][j][k & 1] + dp[i + 2][j - 2][k + 1 & 1] * C(i + 1)) % MOD;
- if(i && j) dp[i][j][k & 1] = (dp[i][j][k & 1] + dp[i][j - 1][k + 1 & 1] * i * (m - i - j + 1)) % MOD;
- }
- }
- }
- for(register int i = 0; i <= m; ++i)
- {
- for(register int j = 0; i + j <= m; ++j)
- {
- ans += dp[i][j][n & 1];
- // cout <<m - i - j << "" << i <<" "<< j <<": " << dp[i][j][n & 1] << endl; // debug
- if(ans>= MOD) ans -= MOD;
- }
- }
- cout << ans;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3157340.html