Happy Necklace

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

Problem Description

Little Q wants to buy a necklace for his girlfriend. Necklaces are single strings composed of multiple red and blue beads. Little Q desperately wants to impress his girlfriend, he knows that she will like the necklace only if for every prime length continuous subsequence in the necklace, the number of red beads is not less than the number of blue beads. Now Little Q wants to buy a necklace with exactly n beads. He wants to know the number of different necklaces that can make his girlfriend happy. Please write a program to help Little Q. Since the answer may be very large, please print the answer modulo 10^9+7. Note: The necklace is a single string, {not a circle}.

Input

The first line of the input contains an integer T(1≤T≤10000), denoting the number of test cases. For each test case, there is a single line containing an integer n(2≤n≤10^18), denoting the number of beads on the necklace.

Output

For each test case, print a single line containing a single integer, denoting the answer modulo 10^9+7.

Sample Input

2 2 3

Sample Output

3 4

Reference Code

#include <cstdio> #include <cstring> const int MOD=1e9+7; typedef long long ll; struct Matrix{ ll matrix[3][3]; Matrix (int x=0){ memset(matrix,0,sizeof(matrix)); if (x==1){ for (int i=0;i<3;++i) matrix[i][i]=1; } } Matrix operator*(const Matrix &oth)const{ Matrix res; for (int i=0;i<3;++i){ for (int j=0;j<3;++j){ ll tmp=0; for (int k=0;k<3;++k){ tmp=(tmp+matrix[i][k]*oth.matrix[k][j])%MOD; } res.matrix[i][j]=tmp; } } return res; } }; Matrix qp(Matrix n,ll k){ Matrix res(1); while (k){ if (k&1) res=res*n; n=n*n; k>>=1; } return res; } ll solve(int f1,int f2,int f3,ll k){ Matrix A; A.matrix[0][0]=1; A.matrix[0][2]=1; A.matrix[1][0]=1; A.matrix[2][1]=1; if (k<=3) return k+1; Matrix res=qp(A,k-3); return (res.matrix[0][0]*f3%MOD+res.matrix[0][1]*f2%MOD+res.matrix[0][2]*f1)%MOD; } int main(){ int t; scanf("%d",&t); while (t--){ ll n; scanf("%lld",&n); printf("%lld\n",solve(2,3,4,n)); } return 0; }

Tips

题意： 一串项链（非环），上有蓝红两色宝石，若蓝色之间不能紧挨着且蓝色之间不能只隔着一个红色，求一共的方法。

题解： 设数组a[]，b[]，c[]分别为后面两个字母为rr，br，rb的字符串的数量。可以得到： $$\begin{array}{rl}a[i]& =a[i-1]+c[i-1]\\ b[i]& =a[i-1]\\ c[i]& =b[i-1]\end{array}$$

因而有： $$\begin{array}{rl}s[n]& =a[n]+b[n]+c[n]\\ & =2\ast a[i-1]+c[i-1]+b[i-1]\\ & =s[n-1]+a[i-1]\\ & =s[n-1]+a[i-2]+c[i-2]\\ & =s[n-1]+a[i-3]+b[i-3]+c[i-3]\\ & =s[n-1]+s[n-3]\end{array}$$

得到递归式：$s[n]=s[n-1]+s[n-3]$ 然后即可用矩阵快速幂求解。