您的位置: 首页  >  文章  >  Happy Necklace（hdu 6030）

Happy Necklace（hdu 6030）

分类: 文章 • 2024-10-31 13:23:34
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




题意：这是典型的矩阵快速幂


只要找出期间的规律就可以 ，我们可以发现序列的结尾只有可能时 01 11 10三个数，因而我们列个表



















长度为偶数的以01 10 11 为结尾的数量




10
11
01





2
1
1
1




4
1+1
1+1+1
1






设ax，bx，cx分别为10 11 01结尾的数量，x为长度


由表我们可以发现10前可由01,11接过来，11前可由01，11，10接过来，01前可由11接过来，故


ax=bx-2 +cx-2;   bx=ax-2 + bx-2 + cx-2;    cx=bx-2;



故可以建立矩阵




Happy Necklace（hdu 6030）


刚才我们只是讨论的偶数的情况，如果是奇数呢


只要把奇数-1变成偶数算出来后，再考虑0 1的情况，可以发现最后是ax+ 2bx + cx(x为奇数减一)


#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <string>
#include <vector>


using namespace std;
typedef long long ll;
const int N = 1e5+9;
const ll mod = 1e9+7;


typedef vector<ll > vec;
typedef vector<vec > mat;


mat mul(mat &A,mat &B)
{
    mat C(A.size(),vec(B[0].size()));
    for(int i=0;i<A.size();i++)
    {
        for(int k=0;k<B.size();k++)
        {
            for(int j=0;j<B[0].size();j++)
            {
                C[i][j] = (C[i][j]+A[i][k]*B[k][j])%mod;
            }
        }
    }
    return C;
}


mat pow(mat A,ll n)
{
    mat B(A.size(),vec(A.size()));
    for(int i=0;i<A.size();i++)
    {
        B[i][i]=1;
    }
    while(n>0)
    {
        if(n&1)B=mul(B,A);
        A=mul(A,A);
        n >>= 1;
    }
    return B;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        ll n;scanf("%lld",&n);
        mat A(3,vec(3));
        A[0][0]=0,A[0][1]=1,A[0][2]=1;
        A[1][0]=1,A[1][1]=1,A[1][2]=1;
        A[2][0]=0,A[2][1]=1,A[2][2]=0;
        ll sum=0;
        if(n&1)
        {
            A = pow(A,(n-3)/2);
            ll a[4]={0,0,0};
            for(int i=0;i<A.size();i++)
            {
                for(int j=0;j<A.size();j++)
                {
                    a[i]=(a[i]+A[i][j])%mod;
                }
            }
            for(int i=0;i<A.size();i++)
            {
                sum=(sum+a[i])%mod;
            }
            sum+=a[1];
        }
        else {
            A = pow(A,(n-2)/2);
            ll a[4]={0,0,0};
            for(int i=0;i<A.size();i++)
            {
                for(int j=0;j<A.size();j++)
                {
                    a[i]=(a[i]+A[i][j])%mod;
                }
            }
            for(int i=0;i<A.size();i++)
            {
                sum=(sum+a[i])%mod;
            }
        }
        printf("%lld\n",sum%mod);
    }
    return 0;
}
															

																					

								

									相关推荐