HDU6030-Happy Necklace

递推+矩阵快速幂

• • 题目：
  • 题意：
  • 分析：
  • （1）写出前几项，找规律：
  • （2）我们逐步分析，从递归的角度出发：
  • 代码：

题目：

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

题意：

有一个有n颗珠子的项链，珠子的颜色为红色和蓝色，要求在该项链的任意素数子链中红色珠子的数量要不少于蓝色珠子的数量，求这n颗珠子的排列方式有多多少种。

分析：

开始看这道题是毫无头绪，因为这珠子的排列方式不知道怎么求。

后来看了各位大佬的博客，总结出两种方法：

（1）写出前几项，找规律：

显而易见，我们立刻就可以推出公式：
F(n)=F(n-1)+F(n-3)

只是因为这道题公式简单，我们才可以用这种方式，所以个人不大推崇！

（2）我们逐步分析，从递归的角度出发：

首先，我们设A代表红珠，B代表蓝珠，最小的素数是2，所以珠子的排列有：
（1）AA
（2）AB
（3）BA
现在我们添加第第三颗珠子：
（1）添加A,显然都是可以的；
（2）添加B,那么AB和BA就不符合要求了，只有AA是符合要求的，那么我们要添加一个B，两个连续的A就是一个硬性的要求；通过观察可以发现，如果我们添加两个A（如果我们当前要添加珠子的位置是n），那么就是符合要求的前n-3个珠子的排列方式的数量。

通过上面的分析，我们就可以归纳出公式：
F(n)=F(n-1)+F(n-3)

题目上的n最大可以到达10的18次方，所以打表肯定不行，每次递推也铁定超时，所以我们就要用矩阵的快速幂，这个就不多说了，上模板就行。

代码：

#include
#include
#define Mod 1000000007using namespace std;struct node{long long map[3][3];
};node Power(node a,node b)
{node c;for(int i=0;i<3;i++){for(int j=0;j<3;j++){c.map[i][j]=0; for(int k=0;k<3;k++){c.map[i][j]+=(a.map[i][k]*b.map[k][j])%Mod;c.map[i][j]%=Mod;}}}return c;
}void Print(long long n)
{node a,b;a.map[0][0]=6;a.map[0][1]=4;a.map[0][2]=3;a.map[1][0]=0;a.map[1][1]=0;a.map[1][2]=0;a.map[2][0]=0;a.map[2][1]=0;a.map[2][2]=0;b.map[0][0]=1;b.map[0][1]=1;b.map[0][2]=0;b.map[1][0]=0;b.map[1][1]=0;b.map[1][2]=1;b.map[2][0]=1;b.map[2][1]=0;b.map[2][2]=0;while(n){if(n&1)a=Power(a,b);n>>=1;b=Power(b,b);}printf("%lld\n",a.map[0][0]%Mod);
}int main()
{int T;long long n;int book[5]={0,0,3,4,6};scanf("%d",&T);while(T--){scanf("%lld",&n);if(n<=4)printf("%d\n",book[n]);elsePrint(n-4);}return 0;} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！