LOJ#2833 「JOISC 2018 Day 1」帐篷 dp

题目描述
译自 JOISC 2018 Day1 T3「テント / Tents」
JOI 君经营着一座露营地。露营地被划分为 H 行 W 列的矩阵，各行平行于东西方向，而各列平行于南北方向。从北向南数第 $i$ 行和从东向西数第 $j$ 列相交的格子表示为 $(i,j)$。

JOI 君想在格子里搭一些帐篷。每座帐篷必须占据刚好一个格子。没有两座帐篷会占据同一个格子。

每座帐篷在东、南、西、北四个方向之一有一个出入口。帐篷的出入口朝向必须满足以下条件：

如果格子 $(i_1,j)和(i_2,j)(1\le i_1<i_2\le H,1\le j\le W)$ 上都有帐篷，那么格子 $(i_1,j)$ 上的帐篷出入口必须朝南，而格子 (i_{2},j) 上的帐篷出入口必须朝北。
如果格子 $(i,j_1)和(i,j_2)(1\le i\le H,1\le j_1<j_2\le W)$ 上都有帐篷，那么格子 $(i,j_1)$ 上的帐篷出入口必须朝东，而格子 $(i,j_2)$ 上的帐篷出入口必须朝西。
JOI 君想知道在露营地上搭起至少一顶帐篷的合法方案数。两种方案被认为是不同的，当且仅当有至少一个格子的状态（即是否存在帐篷或帐篷出入口的朝向）不同。

任务
给出露营地的相关信息，请求出在露营地上搭起至少一顶帐篷的合法方案数，对 1000000007 取模。

输入格式
仅一行两个以空格分开的整数 H 和 W，表示 JOI 君经营的露营地有 H 行 W 列。

输出格式
输出一行，仅一个整数，表示在露营地上搭起至少一顶帐篷的合法方案数对 1000000007 取模的余数。

分析：如果某一行有两顶帐篷，这两顶帐篷出口必须东西相对，那么这两顶帐篷所在的列不可能有其它帐篷（因为要求出口南北相对）。基于此，可以进行一个dp：

假设我们从上往下一行一行放帐篷。设大小为$(i,j)$的营地的方法为$f[i][j]$
在计算$f[i][j]$时，不妨分类讨论：
（1）这一行是空的。这种情况有$f[i-1][j]$种放法。
（2）这一行只有一顶帐篷，且这顶帐篷所在列也只有一顶帐篷。我们先把这一行的帐篷放好，有$4\ast j$种放法（算上方向）。那么这顶帐篷所在行列都不能放帐篷了，剩下$i-1$行和$j-1$列，因此总放法为$4\ast j\ast f[i-1][j-1]$。
（3）这一行有一顶帐篷，且这一列的前面某行也有一顶帐篷，这两顶帐篷南北相对。这一顶帐篷的放法有$j$种，前面行帐篷的方法有$i-1$种。把这两顶帐篷放好后，这两行一列就不能再放帐篷，剩下的放法为$f[i-2][j-1]$。因此总贡献为$j\ast (i-1)\ast f[i-2][j-1]$。
（4）这一行有两顶帐篷，则帐篷所在的两列不能有其它帐篷。同理，总贡献为$\frac{j(j-1)}{2}f[i-1][j-2]$。

注意这样算出的结果可能全空，因此最后答案要减1。

代码：

#include
#include
#include
#include
#define mod 1000000007
using namespace std;
typedef long long ll;
int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9') {
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9') {
		x=10*x+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int Size=3005;
const int INF=0x3f3f3f3f;
const int MOD=10007;
int n,m,dp[Size][Size];
int main() {
	n=read();
	m=read();
	for(int i=0; i<=n; i++)	dp[i][0]=1;
	for(int i=0; i<=m; i++)	dp[0][i]=1;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			dp[i][j]=dp[i-1][j];
			dp[i][j]=(dp[i][j]+4ll*j%mod*dp[i-1][j-1]%mod)%mod;
			if(j>=2)	dp[i][j]=(dp[i][j]+(ll)j*(j-1)/2%mod*dp[i-1][j-2]%mod)%mod;
			if(i>=2)	dp[i][j]=(dp[i][j]+(ll)j*(i-1)%mod*dp[i-2][j-1]%mod)%mod;
		}
	}
	printf("%d",(dp[n][m]-1+mod)%mod);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40