HDU 6030 Happy Necklace (矩阵快速幂)

阅读量：4562 次

发布时间：2019-06-08

本文共 2532 字，大约阅读时间需要 8 分钟。

题目链接：

思路：可以推导出递推式f[i]=f[i-1]+f[i-3],用矩阵快速幂求解即可。

可以参考挑战程序设计竞赛第二版200页详细解释。

代码：

1 const int inf = 0x3f3f3f3f; 2 typedef vector
     
       vec; 3 typedef vector
      
        mat; 4  5 mat mul(mat &A, mat &B){ 6     mat C(A.size(), vec(B[0].size())); 7     for(int i = 0; i < A.size(); i++){ 8         for(int k = 0; k < B.size(); k++){ 9             for(int j = 0; j < B[0].size(); j++){10                 C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;11             }12         }13     }14     return C;15 }16 17 mat pow(mat A, ll n){18     mat B(A.size(), vec(A.size()));19     for(int i = 0; i < A.size(); i++){20         B[i][i] = 1;21     }22     while(n > 0){23         if(n & 1) B = mul(B, A);24         A = mul(A, A);25         n >>= 1; 26     }27     return B;28 }29 30 int main(){31     int t;32     scanf("%d", &t);33     while(t--){34         long long n;35         scanf("%lld", &n);36         mat A(3, vec(3));37         A[0][0] = 1; A[0][1] = 0; A[0][2] = 1;38         A[1][0] = 1; A[1][1] = 0; A[1][2] = 0;39         A[2][0] = 0; A[2][1] = 1; A[2][2] = 0;40         A = pow(A, n - 2);41         ll ans = (A[2][0] * 6 + A[2][1] * 4 + A[2][2] * 3) % mod;42         printf("%lld\n", ans);43     }44 }

题目：

Happy Necklace

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 539 Accepted Submission(s): 236

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