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;
}
没有评论:
发表评论