hiho 1318 非法二进制数 dp

#1318 : 非法二进制数

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

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

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

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

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

输入

一个整数  (1 ≤  ≤ 100)。

输出

 位非法二进制数的数目模109+7的余数。

样例输入

3

样例输出

3

简单的动态规划。

我们可以先算出一共有多少个 合法 的二进制数。 用f[n][x]表示n位二进制数，最后1位是x(x取值0或1)，合法的二进制数的数目。 于是有：

f[n][0] = f[n - 1][0] + f[n - 1][1]

f[n][1] = f[n - 1][0];

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 1000000007

#define pi (4*atan(1.0))

const int N=2e3+,M=1e6+,inf=1e9+;

ll dp[N][];

ll quick(ll a,int x)

{

    ll ans=;

    while(x)

    {

        if(x&)

        ans*=a,ans%=mod;

        x>>=;

        a*=a;

        a%=mod;

    }

    return ans;

}

int main()

{

    int x,y,z,i,t;

    scanf("%d",&x);

    dp[][]=;

    dp[][]=;

    for(i=;i<=x;i++)

    {

        dp[i][]=(dp[i-][]+dp[i-][])%mod;

        dp[i][]=dp[i-][];

    }

    cout<<((quick(,x)-dp[x][]-dp[x][])%mod+mod)%mod<<endl;

    return ;

}