hiho一下 第158周 非法二进制数 （dp）

描述

如果一个二进制数包含连续的两个1，我们就称这个二进制数是非法的。

小Hi想知道在所有 n 位二进制数（一共有2n个）中，非法二进制数有多少个。

例如对于 n = 3,有 011, 110, 111 三个非法二进制数。

由于结果可能很大，你只需要输出模109+7的余数。

输入

一个整数 n (1 ≤ n ≤ 100)。

输出

n 位非法二进制数的数目模10^9+7的余数。

样例输入

3

样例输出

3

思路

令 dp[i][x] 代表长度为 i ，末尾为 x 的合法二进制数的个数，于是非法二进制数个数便是 $2^n-dp[n][0]-dp[n][1]$

对于每一个合法二进制数来说，它的末尾有两种情况： 0 或 1 。

末尾为 0 时可以由前一个状态末尾任意转移而来。

末尾为 1 时只能由前一个状态末尾为 0 转移。

于是便有：

$dp[i][0]=dp[i-1][0]+dp[i-1][1]$

$dp[i][1]=dp[i-1][0]$

AC 代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int mod = 1e9+7;
LL dp[105][2];

void init()
{
    dp[1][0]=dp[1][1]=1;
    for(int i=2; i<=100; i++)
    {
        dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
        dp[i][1]=dp[i-1][0];
    }
}

int main()
{
    init();
    int n;
    while(cin>>n)
    {
        int cnt = (dp[n][0]+dp[n][1])%mod;
        int ans=1;
        for(int i=0; i<n; i++,ans=(ans*2)%mod);
        ans-=cnt;
        if(ans<0)ans+=mod;
        cout<<ans<<endl;
    }
    return 0;
}