給定矩陣$A,B$，且有

$$
f(0) = A ,f(i) =B * \prod_{i=w(i)}^{i-1}f(i)
$$

求f(n)

其中，當w(i)單增時，可以做到$O(n*m^3)$，注意要優化取模運算。

對于加入的f(i)，我們壓入棧中，維護棧的?元素積。

同時維護棧之前的一段元素的后綴積，當w(i)超過非棧元素的右邊界時，將棧內元素暴力化為后綴積。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 #define LL long long 6 #define N 1000010 7 8 using namespace std; 9 10 int P; 11 12 int m,n; 13 14 struct MA 15 { 16 LL a[5][5]; 17 void scan() 18 { 19 for(int i=0,j;i<m;i++) 20 for(j=0;j<m;j++) scanf("%lld",&a[i][j]); 21 } 22 void init() 23 { 24 memset(a,0,sizeof(a)); 25 for(int i=0;i<m;i++) a[i][i]=1; 26 } 27 void print() 28 { 29 for(int i=0;i<m;i++) 30 { 31 for(int j=0;j<m;j++) printf("%lld ",a[i][j]); 32 printf("\n"); 33 } 34 } 35 }A0,B; 36 37 MA sta[N]; 38 MA pre[N]; 39 MA sumv,A; 40 int c[N],tot,r; 41 42 MA mul(MA x,MA y) 43 { 44 MA ans; 45 for(int i=0,j,k;i<m;i++) 46 for(j=0;j<m;j++) 47 { 48 ans.a[i][j]=0; 49 for(k=0;k<m;k++) 50 ans.a[i][j] += x.a[i][k]*y.a[k][j]; 51 } 52 for(int i=0,j;i<m;i++) 53 for(j=0;j<m;j++) ans.a[i][j]%=P; 54 return ans; 55 } 56 57 void build() 58 { 59 int tmp=r; 60 for(int i=1;i<=tot;i++) pre[++r]=sta[i]; 61 tot=0; 62 for(int i=r-1;i>=tmp+1;i--) pre[i]=mul(pre[i], pre[i+1]); 63 sumv.init(); 64 } 65 66 int main() 67 { 68 while(~scanf("%d%d%d",&n,&m,&P)) 69 { 70 A0.scan(); 71 B.scan(); 72 for(int i=1;i<=n;i++) scanf("%d",&c[i]); 73 for(int i=0;i<=n;i++) pre[i].init(); 74 r=0; 75 tot=0; 76 pre[0]=A0; 77 sumv.init(); 78 for(int i=1;i<=n;i++) 79 { 80 if(c[i]>r) build(); 81 A=mul(pre[c[i]],sumv); 82 A=mul(A,B); 83 sta[++tot]=A; 84 sumv=mul(sumv,A); 85 } 86 A.print(); 87 } 88 return 0; 89 } View Code

。

當w(i)不單增時，我們可以維護$8$個長度為$6,6^2,6^3...6^8$的隊列，每一次將新加入的元素先壓入長度為$6$的隊列，并$O(m^3*6)$維護后綴積，當隊列滿了之后，將其作為一個元素加入$6^2$的隊列，同時維護至多$6$個元素的后綴積，當$6^2$滿了之后$O(m^3*6^2)$ 暴力將其變為一個元素（算出$6^2$個元素的后綴積），并作為整體壓入下一序列。

每個元素最多被更新了8次，所以 $O(8*n*m^3)$

?

轉載于:https://www.cnblogs.com/lawyer/p/6443625.html

總結

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

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