hdu 6030 Happy Necklace(矩阵快速幂)

题意：

给你一个有n颗只有红黑的珠子串，对于任意一个连续的质数个珠子，红的珠子都不能少于黑的珠子。

问你有多少个这样的含n颗珠子的串满足这样的条件。

题解：

首先打个表，发现是A_n=A_n-1+A_n-3。

然后直接上矩阵就好了

 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=a;i<=b;i++)
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 const int mat_N=3,mo=1e9+7;
 8 struct mat{
 9     ll c[mat_N][mat_N];
10     void init(){mst(c,0);}
11     mat operator*(mat b){
12         mat M;int N=mat_N-1;M.init();
13         F(i,0,N)F(j,0,N)F(k,0,N)M.c[i][j]=(M.c[i][j]+c[i][k]*b.c[k][j])%mo;
14         return M;
15     }
16     mat operator+(mat b){
17         mat M;int N=mat_N-1;
18         F(i,0,N)F(j,0,N)M.c[i][j]=(c[i][j]+b.c[i][j])%mo;
19         return M;
20     }
21     mat operator^(ll k){
22         mat ans,M=(*this);int N=mat_N-1;ans.init();
23         F(i,0,N)ans.c[i][i]=1;
24         while(k){if(k&1)ans=ans*M;k>>=1,M=M*M;}
25         return ans;
26     }
27 }A;
28 
29 int main()
30 {
31     A=(mat){1,0,1,1,0,0,0,1,0};
32     int t,a[5];
33     a[2]=3,a[3]=4,a[4]=6;
34     scanf("%d",&t);
35     while(t--)
36     {
37         ll n;
38         scanf("%lld",&n);
39         if(n<=4)printf("%d
",a[n]);
40         else
41         {
42             mat ans=A^(n-4);
43             printf("%lld
",(ans.c[0][0]*6+ans.c[0][1]*4+ans.c[0][2]*3)%mo);
44         }
45     }
46     return 0;
47 }

View Code

hdu 6030 Happy Necklace(矩阵快速幂)

相关推荐