題意：
? ? ? 給你一個(gè)關(guān)系式，x[n] = 3*x[n-1] + x[n-2],求x(x(x[n]))%1000000007.


思路：

? ? ? 做這個(gè)題目要明確一點(diǎn)，就是對于取余操作大多數(shù)時(shí)候都會出現(xiàn)循環(huán)節(jié)的情況，尤其是對于像這個(gè)題目的轉(zhuǎn)換公式，數(shù)據(jù)有規(guī)律遞增，那么也就是說0 1 1 ....等再次出現(xiàn)0 1的時(shí)候也就是一定找了循環(huán)節(jié)，對于這個(gè)題目我們找循環(huán)節(jié)主要不是為了防止超時(shí)，而是為了得到正確的答案，因?yàn)閤[n]很大的時(shí)候就的模擬大數(shù)，就麻煩了，我們只要找到每一層的循環(huán)節(jié)，就能把數(shù)據(jù)弄小，就可以跑三次矩陣快速A掉這個(gè)題目了。

下面給出暴力循環(huán)節(jié)代碼（暴力第二層的，最內(nèi)層把10..7改成第二層的MOD就行了）

#include<stdio.h>


int main ()
{
? ?__int64 a = 0 ,b = 1 ,c;
? ?for(__int64 i = 3 ; ;i ++)
? ?{
? ? ? c = (b * 3 + a)%1000000007;
? ? ? a = b ,b = c;
? ? ? if(a == 0 && b == 1)
? ? ? {
? ? ? ? ? printf("%I64d\n" ,i - 2);
? ? ? ? ? break;
? ? ? }
? ?}
? ?getchar();
? ?return 0;
}
? ? ??
暴力后得到最內(nèi)側(cè)的MOD = 183120
第二層 MOD = 222222224
最外層給了 MOD = 1000000007

AC代碼

#include<stdio.h> #include<string.h> __int64 MOD1 = 183120; __int64 MOD2 = 222222224; __int64 MOD3 = 1000000007;__int64 MOD; typedef struct {__int64 mat[5][5]; }A;A mat_mat(A a ,A b) {A c;memset(c.mat ,0 ,sizeof(c.mat));for(int k = 1 ;k <= 2 ;k ++)for(int i = 1 ;i <= 2 ;i ++)if(a.mat[i][k])for(int j = 1 ;j <= 2 ;j ++)c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;return c; } A quick_mat(A a ,__int64 b) {A c;memset(c.mat ,0 ,sizeof(c.mat));c.mat[1][1] = c.mat[2][2] = 1;while(b){if(b & 1) c = mat_mat(c ,a);a = mat_mat(a ,a);b >>= 1;}return c; }int main () {__int64 n ,i;A aa ,bb;aa.mat[1][1] = 0 ,aa.mat[1][2] = 1;aa.mat[2][1] = 1 ,aa.mat[2][2] = 3;while(~scanf("%I64d" ,&n)){if(n == 0){printf("0\n");continue;}if(n == 1){printf("1\n");continue;}MOD = MOD1;bb = quick_mat(aa ,n - 1);n = (0 * bb.mat[1][2] + 1 * bb.mat[2][2])% MOD;if(n == 0){printf("0\n");continue;}if(n == 1){printf("1\n");continue;}MOD = MOD2;bb = quick_mat(aa ,n - 1);n = (0 * bb.mat[1][2] + 1 * bb.mat[2][2])% MOD;if(n == 0){printf("0\n");continue;}if(n == 1){printf("1\n");continue;}MOD = MOD3;bb = quick_mat(aa ,n - 1);n = (0 * bb.mat[1][2] + 1 * bb.mat[2][2])% MOD;printf("%I64d\n" ,n);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4291 暴力循环节+矩阵快速幂的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。