给定一个 $n\cdot m$ 的方格图，每个格子可以被染成黑色或白色，且与其相邻的四个格子中至多只有一个与其颜色相同，求方案数。
我们可以一行一行的考虑 首先假如第一行存在连续的两个1 那么后面的状态就全部可以推出 因为下面两个肯定是0 然后所有状态就可以一步步推出来 相邻没有连续的只有一种情况即101010...注意我们此时只考虑一个大类 实际上01可以取反所以最后算出的状态要乘2
在101010...的情况下 第一行没有影响 所以第一列会产生影响 这种情况和之前一样 所以我们只要考虑第一行或者第一列合法的有多少状态即可 要么一个要么两个 其实这就是斐波那契数列 当然我们也可以写一个dp
f[i][0]表示第i个是黑色 f[i][1]表示第i个是白色 有如下dp式
$f[i][0]=f[i-1][1]+f[i-2][1]$
$f[i][1]=f[i-1][0]+f[i-2][0]$
$f[0][0]=f[0][1]=f[1][1]=f[0][0]=1$
当然这个dp式的值其实就是斐波那契
然后我们算出$f[n]$注意10101..的情况要去掉给列考虑 所以有$f[n]-1$个状态 列又有$f[m]$个状态 最后01取反 所以状态共有$(f[n]+f[m]-1)\cdot 2$
注意由于有减法所以模意义下有可能会变成负数 所以需要(x%p+p)%p这样的操作
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
41
42
43
|
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define mst(a,b) memset((a),(b),sizeof(a))
#define PII pair<int,int>
using namespace std;
template<class T>inline void read(T &x) {
x=0; int ch=getchar(),f=0;
while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
if(f)x=-x;
}
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=100000;
const int maxn=100050;
ll f[maxn][2];
ll n,m;
void init(int n)
{
f[1][1]=1,f[1][0]=1,f[0][0]=1,f[0][1]=1;
for(int i=2;i<=n;i++)
{
f[i][1]=(f[i-1][0]+f[i-2][0])%mod;
f[i][0]=(f[i-1][1]+f[i-2][1])%mod;
}
}
int main()
{
init(N);
cin>>n>>m;
cout<<((((f[n][1]-1+f[m][1])*2)%mod+mod)%mod)<<endl;
return 0;
}
|