題意：
? ? ? ?an=Σ1<=i<=kan-ibi mod 10 000 for n >= k，題意看了好久才懂，有點(diǎn)蛋疼啊，
這個(gè)題目要是能看懂題意就簡(jiǎn)單了，先給你k,然后給你a0 a1 a2 a3 ..ak-1.
然后給你b1 b2 b3 b4 ..bk,然后給你一個(gè)i，讓你輸出ai的值，如果i < k直接輸出輸入時(shí)的ai就行，否則就按照他給的那個(gè)公式
an=Σ1<=i<=kan-ibi mod 10 000 for n >= k


比如k=3
那么 a3 = a2*b1 + a1*b2 + a0*b3
? ? ?a4 = a3*b1 + a2*b2 + a1*b3
? ? ?a5 = a4*b1 + a3*b2 + a2*b3
? ? ?a6 = a5*b1 + a4*b2 + a3*b3
......


下面構(gòu)造矩陣 ，這個(gè)矩陣是k*k的，也就是每次都是變的，但是有規(guī)律，最大是100*100
，拿k=3舉例子


a3 a2 a1 ?0 0 b1 ?a2 a3 a4
? ? ? ? ? 1 0 b2
? ? ? ? ? 0 1 b3


這樣就輕松構(gòu)造這個(gè)矩陣了吧，要是k=4也一樣
0 0 0 b1
1 0 0 b2
0 1 0 b3
0 0 1 b4
....

好啦就說(shuō)這么多，最近在忙活寫(xiě)服務(wù)器玩，去寫(xiě)自己的服務(wù)器嘍......

#include<stdio.h> #include<string.h>#define MOD 10000typedef struct {int mat[110][110]; }M;M matM(M a ,M b ,int n) {M c;memset(c.mat ,0 ,sizeof(c.mat));for(int k = 1 ;k <= n ;k ++)for(int i = 1 ;i <= n ;i ++)if(a.mat[i][k])for(int j = 1 ;j <= n ;j ++)c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;return c; }M qPowMat(M a ,int b ,int n) {M c;memset(c.mat ,0 ,sizeof(c.mat));for(int i = 1 ;i <= n ;i ++)c.mat[i][i] = 1;while(b){if(b & 1) c = matM(c ,a ,n);a = matM(a ,a ,n);b >>= 1;}return c; }int main () {int k ,n ,i ,j;int A[105] ,B[105];M star ,ans;while(~scanf("%d" ,&k) && k){for(i = 0 ;i < k ;i ++)scanf("%d" ,&A[i]);for(i = k ;i >= 1 ;i --)scanf("%d" ,&B[i]);scanf("%d" ,&n);if(n < k){printf("%d\n" ,A[n]);continue;}memset(star.mat ,0 ,sizeof(star.mat));for(i = 1 ;i < k ;i ++)star.mat[i+1][i] = 1;for(i = 1 ;i <= k ;i ++)star.mat[i][k] = B[i];ans = qPowMat(star ,n - k + 1 ,k);int sum = 0;for(i = 1 ;i <= k ;i ++)sum = (sum + A[i-1] * ans.mat[i][k]) % MOD;printf("%d\n" ,sum);}return 0; }

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的POJ2118基础矩阵快速幂的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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