2016年8月27日星期六

Consecutive 1's not allowed

Problem
   Count number of binary strings without consecutive 1’s.

Solution
 a[i] means string ends with 0 && not contains  11;
 b[i] means string ends with 1 && not contains 11;
 c[i] means string ends with 11 or contains 11;

Code
#include <stdio.h>
#include <iostream>
using namespace std;
const int N = 75;
long long a[N],b[N],c[N];
int T;
int n;
const int mod = 1e9 + 7;
int main() {
 a[1] = 1;
 b[1] = 1;
 c[1] = 0;
 for (int i = 2;i <= 70;i ++) {
     a[i] = (a[i - 1] + b[i - 1]) % mod;
     b[i] = a[i - 1] % mod;
     c[i] = (2 * c[i - 1] + b[i - 1]) % mod;
 }
 cin >> T;
 int n;
 while (T --) {
     cin >> n;
     cout << (a[n] + b[n]) % mod << endl;
 }
 return 0;
}

没有评论:

发表评论