[loj 2833]「JOISC 2018 Day 1」帐篷

题目链接

https://loj.ac/problem/2833

题解

我们设 \(f_{i,j}\) 表示填完 \(i\) 行 \(j\) 列的方案数。

对于当前行，我们有如下四种决策：

1. 啥都不放：\(f_{i-1,j}\)；
2. 放一个帐篷单独占据一列（方向任意）：\(4 \times j \times f_{i-1,j-1}\)；
3. 在同一行放两个帐篷占据两列：\(\frac{j(j-1)}{2} \times f_{i-1}{j-2}\)；
4. 在同一列放两个帐篷占据两行：\((i-1) \times j \times f_{i-2,j-1}\)；

时间复杂度 \(O(HW)\)。

#include <iostream>
#define MOD 1000000007
using namespace std;
long long f[3005][3005];
int main()
{
 int h,w;
 cin>>h>>w;
 for(int i=0;i<=h;i++)
  f[i][0]=1;
 for(int i=0;i<=w;i++)
  f[0][i]=1;
 for(int i=1;i<=h;i++)
  for(int j=1;j<=w;j++)
  {
   f[i][j]=f[i-1][j];
   f[i][j]=(f[i][j]+4*j*f[i-1][j-1])%MOD;
   if(i>=2)
    f[i][j]=(f[i][j]+f[i-2][j-1]*j*(i-1))%MOD;
   if(j>=2)
    f[i][j]=(f[i][j]+f[i-1][j-2]*j*(j-1)/2)%MOD;
  }
 cout<<(f[h][w]-1+MOD)%MOD<<endl;
 return 0;
}