如果一个01字符串满足不存在010这样的子串，那么称它为非010串。
求长度为n的非010串的个数。(对1e9+7取模)
Input
一个数n，表示长度。(n<1e15)
Output
长度为n的非010串的个数。(对1e9+7取模)
Input示例
3
Output示例
7
解释:
000
001
011
100
101
110
111
#include <iostream>
#include <cstring>
using namespace std;
const long long int MOD = 1e9+7;
struct matrix
{
long long int val[4][4];
void clean()
{
memset(val, 0, sizeof(val));
}
void init()
{
memset(val, 0, sizeof(val));
for (int i = 0; i < 4; i++)
{
val[i][i] = 1;
}
}
matrix operator *(const matrix &a)
{
matrix result;
result.clean();
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
for (int k = 0; k < 4; k++)
{
result.val[i][j] += val[i][k]*a.val[k][j];
result.val[i][j] %= MOD;
}
}
}
return result;
}
};
matrix fun(long long int n, matrix &base)
{
matrix result;
result.init();
while (n > 0)
{
if (n & 1)
{
result = result * base;
}
base = base * base;
n >>= 1;
}
return result;
}
int main()
{
long long int n;
cin >> n;
matrix base =
{
1, 1, 0, 1,
1, 0, 0, 0,
0, 1, 0, 0,
0, 0, 1, 0
};
matrix result;
result.clean();
result.val[0][0] = 7;
result.val[1][0] = 4;
result.val[2][0] = 2;
result.val[3][0] = 1;
if (n <= 3)
{
cout << result.val[3-n][0] << endl;
}
else
{
base = fun(n-3, base);
result = base * result;
cout << result.val[0][0] << endl;
}
return 0;
}
