codeforces 594 div2 Ivan the Fool and the Probability Theory （DP 推公式）

题目大意：

现在有n*m个格子。然后我们可以对这些格子染上黑色或者白色。规定每个格子最多允许相邻1个与它同样颜色的格子，问你我们有多少中不同的染色方案。

解题思路：

首先考虑1*m的情况。我们可以定义状态：

i为这一行的第i个，state为0和1表示染上白色还是黑色，表示走到第i个的并且当前颜色为黑色或者白色时候我们有多少种染色方案。

边界条件：

为什么可以这样递推呢？我们发现：比如当前是黑色，那么只有三种可能

其中第一行和第三行对应dp[i-1][!state]的情况。第二行代表dp[i-2][!state]的计数。

所以能够得到这个递推。

接着我们需要证明任意两行只可能完全同色或者反色。我们在这里可以做一个反证法。

假如第i行和第i-1行有部分颜色相同，部分颜色不同。那么我们总是可以找出一条交界线即一边是变化另一边是没有变化 如下：

那么我们总是能找到一个矛盾的方块。例如上面画红色线的框就是矛盾点。定理得证。所以假如第一行有两个颜色相同的连在一起的方块，那么它对总的方案数贡献只有一种，因为它只能是不断反色交替。

那么第一行有多少种连色方案数呢？是dp[m][1]+dp[m][0]-2种，因为只有两种情况是不符合的：01010101，还有10101010交替的这两种。所以 ans = dp[m][1]+dp[m][0]-2 + X. X为0101；1010这种交替出现的对答案贡献数。

我们发现：这两种方案的贡献数，相当于行的可行方案的数目即dp[n][0]+dp[n][1]。

所以

ans=dp[m][1]+dp[m][0]-2+dp[n][0]+dp[n][1]

废话：

首先这道题我们必须有递推公式的思想。我们需要发现当前的计数方案和之前的计数方案是加法的关系。

另外，这题还需要对定理的一个证明。这是最难想到的。但是这也为我们做题开辟了一个新思路。当题目无从下手时，我们是不是可以通过证明一些定理来入手呢？当然这里的定理要能构思出来是最难的。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MODN=1e9+7;
const int MAXN=1e5+10;
int memo[MAXN][2];
int dfs(int level,int state){
  
  if(memo[level][state]!=-1)return memo[level][state];
  return memo[level][state]=(dfs(level-1,!state)+dfs(level-2,!state))%MODN;
}
int32_t main(){
  int n,m;cin>>n>>m;
  for(int i=0;i<MAXN;i++)
    for(int j=0;j<2;j++)
      memo[i][j]=-1;
  memo[0][0]=memo[0][1]=1;
  memo[1][1]=memo[1][0]=2;
  dfs(max(n-1,m-1),1);
  dfs(max(n-1,m-1),0);
  
  //cerr<<memo[m-1][0]<<" "<<memo[m-1][1]<<endl; 
  int ans=(memo[m-1][0]+memo[m-1][1]-2+memo[n-1][0]+memo[n-1][1]+MODN)%MODN;
  cout<<ans<<endl;
  return 0;
}