思路
注意到重要性质：每确定一对帐篷，那么这对帐篷所在行和列不能放置其他帐篷，这将解释后来的方案之间为什么不会互相冲突。
考虑设计 \(dp_{ i , j }\) 表示营地大小 \(i\) 行 \(j\) 列时的方案数，逐行计算，对于每一行的放置：
-
若第 \(i\) 行不放，直接转移 \(dp_{ i , j } + = dp_{ i - 1 , j }\)
-
若第 \(i\) 行放置一个，所在列没有其他帐篷，首先从 \(j\) 个位置里选出一个位置来放置，且由于所在行与列均没有其他帐篷，方向任取，那么 \(dp_{ i , j } + = \binom { j } { 1 } \times 4 \times dp_{ i - 1 , j - 1 }\)
-
若第 \(i\) 行放置一个，与同列异行另一个帐篷配对，相比前一种情况方向不能任取，且需要乘上从前 \(i - 1\) 行里选出一行放置与之配对的帐篷的方案数，有 \(dp_{ i , j } + = \binom {j} { 1 } \times \binom { i - 1 } { 1 } \times dp_{ i - 2 , j - 1 }\)
-
若第 \(i\) 行放置两个，则方向固定，只需 \(dp_{ i , j } + = \binom { j } { 2 } \times dp_{ i - 1 , j - 2 }\)
代码实现就很简单啦，我这里为了显示思路预处理了组合数，实际实现过程中 \(\times \binom { i } { 1 }\) 可以直接写作 \(\times i\)，注意保证方案不能为空，答案需要减一。
Code
#include<iostream>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=3005;
const int MOD=1e9+7;
int n,m,fac[N],inv[N],dp[N][N];
int Quick_Pow(int a,int b)
{int res=1,base=a;while(b){if(b&1) res=1ll*res*base%MOD;base=1ll*base*base%MOD;b>>=1;}return res;
}
void Init(int n)
{fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%MOD;inv[n]=Quick_Pow(fac[n],MOD-2);for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%MOD;
}
int C(int n,int m)
{return 1ll*fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main()
{IOS;cin>>n>>m;Init(max(n,m));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]+1ll*C(j,1)*4*dp[i-1][j-1]%MOD)%MOD;//放一个，且所在列没有其他帐篷dp[i][j]=(dp[i][j]+(i>=2)*1ll*C(j,1)*C(i-1,1)*dp[i-2][j-1]%MOD)%MOD;//放一个，与所在列另一帐篷相对dp[i][j]=(dp[i][j]+(j>=2)*1ll*C(j,2)*dp[i-1][j-2]%MOD)%MOD;//放两个}}cout<<dp[n][m]-1<<'\n';return 0;
}
完结撒花～