01串也疯狂之光棍也有伴

Description

话说春节那天，小明和晓明在实验室刷题。刷着刷着小明觉得累了，就邀请晓明一起看春晚。晓明觉得小明很无聊，不想理小明，但是小明很会磨嘴皮子，晓明耐不住小明的胡嘴蛮缠，于是和小明一起看起春晚来。

小明顿时觉得倍儿爽啊！可是一看，“wocao”，“最炫小苹果”，小明顿时觉得很伤心。 “连小苹果都有伴了。。。呜呜。。。。” 晓明看到小明哭了，就想安慰他，可是怎么安慰呢！
晓明陷入了沉思，忽然，晓明灵光一闪，想借一下出题名义，让小明开心起来。于是晓明对小明说，既然小苹果都有伴了，那我们两光棍离脱单也不远了吧！。。。。噼噼啪啦，晓明对小明说不然我们也来让光棍有个伴吧！正好，正值我们学校的校赛，我们就以光棍为名，来出一道题。小明听到要出题，立马起了劲。。。他们认为“11”是光棍成双成对的标志，于是，小明和晓明想问下你们，对于一个长度为n的01串，到底有多少串是含有“11”子串的呢？。。。聪明的你，相信你已想到怎么AC了。
例如长度为2的有“11”一个符合条件的01串；
        长度为3的有“111”，“110”，“011”三个符合条件的串;

长度为4的有“1111”，“1101”，“1100”，“0011”，“1011”，“0111”，“0110”，“1110”八个符合条件的串。

Input

有T组数据输入。(T<=1000);
每组数据只有一行，一个正整数n(1<=n<=10^6)

Output

对于每组数据输出一行结果，对1000000007取模。

Sample Input

3 1 4 5

Sample Output

0 8 19

HINT

这题直接dp不太好做，考虑反面，求含有11的串。

就是总串数-不含有11的串。

而设dp[i]表示位数为i但是不含有11的串。

考虑第i位，如果为0，那么dp[i] = dp[i-1].

如果为1，那么第i-1位必须要为0. dp[i] = dp[i-2]

所以dp[i] = dp[i-1] + dp[i-2]

所以不含有11的串 dp2[i] = 2^n - dp[i]。

且加法乘法减法对取模都没有影响。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <string>
 5 #include <algorithm>
 6 using namespace std;
 7 long long n;
 8 long long dp[1000010], dp2[1000010];
 9 void init(){
10     dp[1] = 2; dp[2] = 3;
11     for(int i = 3; i <= 1000000; i++) dp[i] = (dp[i-1]%1000000007 + dp[i-2]%1000000007)%1000000007; 
12     
13     long long mul = 2;
14     for(int i = 1; i <= 1000000; i++){
15         if(mul <= dp[i]){
16             mul = mul + 1000000007;
17             dp2[i] = (mul - dp[i])%1000000007;
18         }
19         else{
20             dp2[i] = (mul - dp[i])%1000000007;
21         }
22         mul = (mul*2)%1000000007;
23     }
24 }
25 int main(){
26     int T;
27     init();
28     scanf("%d", &T);
29     while(T--){
30         
31         cin>>n;
32         cout<<dp2[n]<<endl;
33     } 
34     return 0;
35 }