『算法-ACM 竞赛』矩阵快速幂–HDU 6030 Happy Necklace

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 109+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≤1018), 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 109+7.

Sample Input
2
2
3

Sample Output
3
4
题意： 给出红蓝两种，然后排成一个字符串，要求在每一个长度为素数的区间里面是的 r(red)的数量不小与 b(blue)的数量;

思路：想象当 n 为 2 的时候的情况是 rr,rb,br,三种情况，当 n 为 3 的时候相当于在后面添加一个 b 或者 r,会发现形成 rr 的情况是前面 rr 和 br 的和，形成 br 的情况是前面的 rb，而形成 rb 的情况是前面的 rr,不能有前面的 br 形成 rb，因为在素数为 3 的时候不能形成 brb；

所以你会发现这个针对的素数只是 2 和 3；

根据递推，设数组 a[],b[],c[]分别为后面两个字母为 rr,br,rb 的字符串的数量，那么可以得到递推式：

a[i] = a[i - 1] + c[i - 1];b[i] = a[i - 1];c[i] = b[i - 1];

而题中要求的是所有的字符串，即 s[n] = a[n] + b[n] + c[n]；

可以得出 s[i] = s[i - 1] + s[i - 3];

n 的范围是 10^18，那么只能用到矩阵快速幂： 可以推出最初的矩阵为

1 0 1
1 0 0
0 1 0

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
struct martix{
    ll mo[4][4];
    martix(){
        memset(mo,0,sizeof(mo));
    }
};
martix mul(martix a,martix b){
    martix c;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            for(int k=0;k<4;k++){
                c.mo[i][j]=(c.mo[i][j]+a.mo[i][k]*b.mo[k][j])%mod;
            }
        }
    }
    return c;
}
ll powmod(martix a,ll n){
    martix T;
    for(int i=0;i<4;i++){
        T.mo[i][i]=1;
    }
    while(n){
        if(n&1) T=mul(a,T);
        n>>=1;
        a=mul(a,a);
    }
    return (T.mo[0][0]*6+T.mo[0][1]*4+T.mo[0][2]*3)%mod;
}
int main()
{
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        int ans[5]={0,0,3,4,6};
        if(n<=4){
            cout<<ans[n]%mod<<endl;
        }
        else{
            martix q;
            q.mo[0][0]=q.mo[0][2]=q.mo[3][2]=q.mo[1][0]=q.mo[2][1]=q.mo[3][2]=1;
            cout<<powmod(q,n-4)%mod<<endl;
        }
    }
    return 0;
}