类型：DP
传送门：>Here<
题意：给出一个$N*M$的棋盘，每行每列的棋子数不得超过$2$。求方案数
解题思路
这题的关键在于如何定义$dp$数组
考虑一行一行做，我们会发现对于第$i$行的方案数不取决于前面棋子的摆放顺序或特定位置，只取决于前面的每一列有多少棋子——只有每一列的棋子个数会影响当前这一行摆放的方案数。于是，令$dp[i][j][k]$表示前$i$行中，有$j$列含有$1$个棋子，$k$列含有$2$个棋子的方案数。我们可以形象地理解为：目前在放第$i$行的棋子，并且前面每一列的棋子数都已确定，现在我们要将棋子接在特定几列上
由于每行的棋子数不超过$2$，因此当前这一行最多放$2$个棋子。因此可以分类讨论：
- 放0枚棋子
选择继承 $$dp[i][j][k]+=dp[i-1][j][k]$$
- 放1枚棋子，在之前没有任何棋子的一列上
放了之后将会增加有一枚棋子的一列，并且共有$M-k-(j-1)$中空列的选择 $$dp[i][j][k]+=dp[i-1][j-1][k] * (M-k-(j-1))$$
- 放1枚棋子，在之前有一枚棋子的一列上
增加一列$2$枚的，减少一列$1$枚的，有$j+1$种选择 $$dp[i][j][k]+=dp[i-1][j+1][k-1] * (j+1)$$
- 放2枚棋子，都放在之前没有棋子的两列上
增加两列$1$枚的，有$C_{M-k-(j-2)}^{2}$种选择 $$dp[i][j][k]+=dp[i-1][j-2][k] * C_{M-k-(j-2)}^{2}$$
- 放2枚棋子，都放在之前有一枚棋子的两列上
增加两列$2$枚的，减少两列$1$枚的，有$j+2$种选择 $$dp[i][j][k]+=dp[i-1][j+2][k-2] * (j+2)$$
- 放2枚棋子，一枚放在之前没有棋子的那列，一枚放在之前有一枚棋子的那列
增加一列$1$枚的，增加一列$2$枚的，减少一列$1$枚的，总和起来增加一列$2$枚的，有$(M-(k-1)-j) * j / 2$种选择 $$dp[i][j][k]+=dp[i-1][j][k-1]*(M-(k-1)-j) * j / 2$$
注意判断边界情况……
本题的初始化是$dp[0][0][0]=1$。网上的文章都很少有对$DP$初始化的详细解释，我的理解是这样的：第一列在转移时不可能出现$k > 0$的情况，因为总共只有$1$行能放。换言之，第一行之前什么都没有。因此只能从$dp[0][0][0]$转移而来
我觉得关于$DP$初始化的问题还是很重要的，比如背包问题中是否恰好装满的问题。关于这方面的知识还需要慢慢积累！
Code
可能中间乘方案数的时候会乘爆，因此需要ll
/*By DennyQi 2018.8.17*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #define r read() #define Max(a,b) (((a)>(b)) ? (a) : (b)) #define Min(a,b) (((a)<(b)) ? (a) : (b)) using namespace std; typedef long long ll; #define int ll const int MAXN = 10010; const int MAXM = 27010; const int INF = 1061109567; const int MOD = 9999973; inline int read(){ int x = 0; int w = 1; register int c = getchar(); while(c ^ '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c >= '0' && c <= '9') x = (x<<3) + (x<<1) + c - '0', c = getchar();return x * w; } int N,M,ans; int dp[105][105][105]; #undef int int main(){ #define int ll N=r,M=r; dp[0][0][0] = 1; for(int i = 1; i <= N; ++i){ for(int j = 0; j <= M; ++j){ for(int k = 0; j + k <= M; ++k){ dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k]) % MOD; if(j-1 >= 0){ dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-1][k] * (M-k-j+1)) % MOD; } if(j+1 <= M && k-1 >= 0){ dp[i][j][k] = (dp[i][j][k] + dp[i-1][j+1][k-1] * (j+1)) % MOD; } if(j-2 >= 0){ dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-2][k] * (M-k-j+2) * (M-k-j+1) / 2) % MOD; } if(j-1 >= 0 && k-1 >= 0){ dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k-1] * (M-k-j+1) * (j)) % MOD; } if(j+2 <= M && k-2 >= 0){ dp[i][j][k] = (dp[i][j][k] + dp[i-1][j+2][k-2] * (j+2) * (j+1) / 2) % MOD; } } } } for(int j = 0; j <= M; ++j){ for(int k = 0; k <= M; ++k){ if(j+k <= M){ ans = (ans + dp[N][j][k]) % MOD; } } } printf("%lld", ans); }