題目：http://acm.hdu.edu.cn/showproblem.php?pid=6030

題意：給出紅藍兩種，然后排成一個字符串，要求在每一個長度為素數的區間里面是的r(red)的數量不小與b(blue)的數量;

解法：難點在于如何找規律。容易推知只要長度為2或3的字符串滿足r>=b，那么之后的素數（5、7......）都會滿足r>=b。

假設現在有一個n字符的串，其方案數為f(n)，考慮一下能否從f(n-1)推得f(n)？

情況1.如果這個串最后一個字符是r，那么倒數第二個既可以是r也可以是b。所以此時f(n) = f(n-1).

情況2.如果這個串最后一個字符是b，那么倒數第二個一定是r才可以滿足“長度為2且r>=b”的條件，那么倒數第三個就一定是r，否則不滿足“長度為3且r>=b”的條件。所以此時f(n) = f(n-3)

綜上，可得f(n) = f(n-1) + f(n-3).

由于輸入量巨大（10¹⁸），所以用數組儲存遞推結果是不可行的，而每次遞推又太慢，所以只能用矩陣快速冪來解決。

由于遞推式中出現f(n-3),所以傳遞矩陣一定是3*3的。

經過推導可得傳遞矩陣為

1 1 0

0 0 1

1 0 0

AC：

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <vector> using namespace std; typedef long long ll; const ll m = 1000000000+7; const int N = 4; struct mar {ll a[N][N]; };//結構化矩陣 mar mul(mar x,mar y) {mar temp;for(int i = 1 ; i < N ; i++)for(int j = 1 ; j < N ; j++)temp.a[i][j] = 0;for(int i = 1 ; i < N ; i++)for(int j = 1 ; j < N ; j++)for(int k = 1 ; k < N ; k++)temp.a[i][j] += (x.a[i][k]%m*y.a[k][j]%m)%m;return temp; }//矩陣乘法 mar quickpow(mar a,ll n) {mar res;res.a[1][1] = 1; res.a[1][2] = 0; res.a[1][3] = 0;res.a[2][1] = 0; res.a[2][2] = 1; res.a[2][3] = 0;res.a[3][1] = 0; res.a[3][2] = 0; res.a[3][3] = 1;//初始化為單位矩陣while(n){if(n&1) res = mul(res,a);a = mul(a,a);n>>=1;}return res; }//矩陣快速冪核心代碼int main() {int t;ll n;cin >> t;while(t--){cin >> n;if(n==2) {cout << 3 <<endl;continue;}mar A;A.a[1][1] = 1; A.a[1][2] = 0; A.a[1][3] = 1;A.a[2][1] = 1; A.a[2][2] = 0; A.a[2][3] = 0;A.a[3][1] = 0; A.a[3][2] = 1; A.a[3][3] = 0;//構造傳遞矩陣mar res = quickpow(A,n-2);cout << ((res.a[1][1] + res.a[1][2] + res.a[1][3]) % m+ (res.a[2][1] + res.a[2][2] + res.a[2][3]) % m+(res.a[3][1] + res.a[3][2] + res.a[3][3]) % m)%m <<endl;}return 0; }

?

轉載于:https://www.cnblogs.com/zz990728/p/8886380.html

總結

以上是生活随笔為你收集整理的HDU 6030 Happy Necklace的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。