Happy Necklace (矩阵快速幂 + 递推 + 取模)

出门莫恨无人随，书中车马多如簇。这篇文章主要讲述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 Input2
2 3 Sample Output3
4 Source 2017中国大学生程序设计竞赛 - 女生专场递推公式: f[n] = f[n - 1] + f[n - 3];

文章图片

1 #include< iostream> 2 #include< cstring> 3 #include< cstdio> 4 using namespace std; 5 struct matrix{ 6long long int mat[4][4]; 7 }A,B; 8 matrix mul(matrix a,matrix b){ 9matrix tmp; 10memset(tmp.mat,0,sizeof(tmp.mat)); 11for(int i = 0; i < 4; i++) 12for(int j = 0; j < 4; j++) 13for(int k = 0; k < 4; k++){ 14tmp.mat[i][j] += a.mat[i][k] * b.mat[k][j]; 15tmp.mat[i][j] %= 1000000007; 16} 17return tmp; 18 } 19 matrix pow_mat(matrix a,long long int n){ //注意n 是long long int 类型,老写成int 类型 20matrix ans; 21int num = 0; 22memset(ans.mat,0,sizeof(ans.mat)); 23for(int i = 0; i < 4; i++) 24ans.mat[i][i] = 1; 25while(n){ 26if(n & 1) 27ans = mul(ans,a); 28a = mul(a,a); 29n > > = 1; 30} 31return ans; 32 } 33 int main(){ 34long long int t,n; 35scanf("%lld",& t); 36while(t--){ 37scanf("%lld",& n); 38if(n == 2){ 39printf("3 "); 40continue; 41} 42else if(n == 3){ 43printf("4 "); 44continue; 45} 46else if(n == 4){ 47printf("6 "); 48continue; 49} 50else if(n == 5){ 51printf("9 "); 52continue; 53} 54else{ 55A.mat[0][0] = 3,A.mat[0][1] = 4,A.mat[0][2] = 6,A.mat[0][3] = 9; 56B.mat[0][0] = 0,B.mat[0][1] = 0,B.mat[0][2] = 1,B.mat[0][3] = 0; 57B.mat[1][0] = 1,B.mat[1][1] = 0,B.mat[1][2] = 0,B.mat[1][3] = 1; 58B.mat[2][0] = 0,B.mat[2][1] = 1,B.mat[2][2] = 1,B.mat[2][3] = 0; 59B.mat[3][0] = 0,B.mat[3][1] = 0,B.mat[3][2] = 0,B.mat[3][3] = 1; 60B = pow_mat(B,n - 5); 61printf("%lld ",mul(A,B).mat[0][3]); 62} 63} 64return 0; 65 }

View Code【Happy Necklace (矩阵快速幂 + 递推 + 取模)】