题意
给定一个$n \times m$的网格图,每个格子只能染黑或白色(1或0),每个格子至多与上下左右格子的一个同色,求方案数。
思路
根据样例可以推得,只要确定第一行和第一列,就确定了整个图形
算法 $(dp)$ $O(n)$
考虑确定一行排列的方案数
$f[i]$表示第$1$行第$i$个方格为$1$的方案数
$f[1]=1$,$(1,1)$为$1$
$f[2]=2$,$(1,1)$可以为$1$或$0$
因为第$i-1$和$i-2$个格子都可以为1
转移方程为$f[i]=f[i-1]+f[i-2]$
行和列等价
所以$n$行$m$列确定的方案数为$f[n]+f[m]$
但行列拼在一起时若行$(1,1),(1,2)$为1,列$(1,1)(1,2)$也为1,$(1,1)$格子不合法,因此要去掉这一种情况
1和0等价所以答案数$\times$2
最后答案数为 $2\times (f[n]+f[m]-1) $
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
int n,m;
ll f[maxn];
int main()
{
f[1]=1,f[2]=2;
for(int i=3;i<maxn;i++) f[i]=(f[i-1]+f[i-2])%mod;
scanf("%d%d",&n,&m);
cout<<(f[n]+f[m]-1)*2ll%mod<<endl;
return 0;
}