Matrix Recurrence

给定矩阵$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)超过非栈元素的右边界时，将栈内元素暴力化为后缀积。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define LL long long

 #define N 1000010

 using namespace std;

 int P;

 int m,n;

 struct MA

 {

         LL a[][];

         void scan()

         {

                 for(int i=,j;i<m;i++)

                         for(j=;j<m;j++) scanf("%lld",&a[i][j]);

         }

         void init()

         {

                 memset(a,,sizeof(a));

                 for(int i=;i<m;i++) a[i][i]=;

         }

         void print()

         {

                 for(int i=;i<m;i++)

                 {

                         for(int j=;j<m;j++) printf("%lld ",a[i][j]);

                         printf("\n");

                 }

         }

 }A0,B;

 MA sta[N];

 MA pre[N];

 MA sumv,A;

 int c[N],tot,r;

 MA mul(MA x,MA y)

 {

         MA ans;

         for(int i=,j,k;i<m;i++)

                 for(j=;j<m;j++)

                 {

                         ans.a[i][j]=;

                         for(k=;k<m;k++)

                                 ans.a[i][j] += x.a[i][k]*y.a[k][j];

                 }

         for(int i=,j;i<m;i++)

                         for(j=;j<m;j++) ans.a[i][j]%=P;

         return ans;

 }

 void build()

 {

         int tmp=r;

         for(int i=;i<=tot;i++) pre[++r]=sta[i];

         tot=;

         for(int i=r-;i>=tmp+;i--) pre[i]=mul(pre[i], pre[i+]);

         sumv.init();

 }

 int main()

 {

         while(~scanf("%d%d%d",&n,&m,&P))

         {

                 A0.scan();

                 B.scan();

                 for(int i=;i<=n;i++) scanf("%d",&c[i]);

                 for(int i=;i<=n;i++) pre[i].init();

                 r=;

                 tot=;

                 pre[]=A0;

                 sumv.init();

                 for(int i=;i<=n;i++)

                 {

                         if(c[i]>r) build();

                         A=mul(pre[c[i]],sumv);

                         A=mul(A,B);

                         sta[++tot]=A;

                         sumv=mul(sumv,A);

                 }

                 A.print();

         }

         return ;

 }

。

当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)$

巴特西

Matrix Recurrence

最新文章

热门文章