hiho #1318 非法二进制数

#1318 : 非法二进制数

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

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

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

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

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

输入

一个整数  (1 ≤  ≤ 100)。

输出

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

样例输入

3

样例输出

3

 #include <iostream>

 typedef long long LL;

 using namespace std;

 int main() {

     int n, mod = ;

     LL s[], pow2 = ;

     s[] = s[] = ;

     cin >> n;

     for (int i = ; i <= n; ++i) {

         s[i] = (s[i - ] + s[i - ] + pow2) % mod;

         pow2 = (pow2 * ) % mod;

     }

     cout << s[n] << endl;

     return ;

 }