题解：AT_joisc2018_c テント (Tents)

· · 题解

水个题解。

简单 DP。考虑从上到下填帐篷，定义 dp_{i,j} 为若当前矩阵还剩下 i 行没填，j 列没填，其他行和列固定的方案数。初始化 dp_{n,m}=1，其余未计算，答案为 \sum\limits_{i=0}^{m-1}dp_{0,i}。

可以跳过一行，从 dp_{i+1,j} 转移来，系数是 1。

可以在这一行放两个配对帐篷，从 dp_{i+1,j+2} 转移来，系数是 \binom{j+2}2。

可以在这一行放一个自由帐篷，从 dp_{i+1,j+1} 转移来，系数是 4\times j。

可以放一个帐篷然后在下面的行再选一个配对，从 dp_{i+2,j+1} 转移来，想象我们“抽走”最上面的一行和下面的任选一行，然后再选一个列，因此系数是 (i+1)\times(j+1)。

如果上面的东西没想清楚，可能需要花多一些的时间调试，出题人很没素质，给点样例不是太弱就是太大，如果调不出来建议复制题解自己随便手敲一些数对比题解输出和自己的输出。

最终代码并不长。

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int n, m;
unsigned long long dp[3005][3005], ans;
signed main() {
    cin >> n >> m;
    for (int i = 0; i <= n; i++) {
        dp[i][m] = 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            dp[i][j] += dp[i + 1][j];
            dp[i][j] += dp[i + 1][j + 2] * ((j + 2) * (j + 1) >> 1);
            dp[i][j] += dp[i + 1][j + 1] * ((j + 1) << 2);
            dp[i][j] += dp[i + 2][j + 1] * ((i + 1) * (j + 1));
            dp[i][j] %= mod;
        }
    }
    for (int i = 0; i < m; i++) {
        ans += dp[0][i];
    }
    cout << ans % 1000000007;
    return 0;
}