[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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据