题意：
\(M_i\)为一个\(m*m\)矩阵，已知
\[
\begin{aligned}
&M_0=A\&M_i=(\prod_{j=c_i}^{i+1}M_j)B
\end{aligned}
\]
问\(M_n\)矩阵，输入包含\(n,m,A,B,c_1\cdots c_n(c_1\leq c_2\cdots \leq c_n)\)。
思路：
因为\(c_1\leq c_2\cdots \leq c_n\)，所以我们只需实现一个队列，满足能从队头\(pop\)，从队尾\(push\)，并且能求队列内乘积。可以通过两个栈实现。
栈\(suf\)保存的是后缀的乘积，\(pre\)保存的是前缀的乘积，那么\(push\)时放到\(pre\)维护前缀积并储存放进去的矩阵，\(pop\)时直接把\(suf\)最前面的后缀弹出即可。如果\(suf\)空了，那么把\(pre\)里的内容暴力变成后缀放到\(suf\)里。可以知道每个矩阵最多进两次栈，复杂度\(O(nm^2)\)。
代码：
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 5;
const int M = 50 + 5;
const ull seed = 131;
const int INF = 0x3f3f3f3f;
const ll MOD = 1000000007;
struct Mat{
int s[5][5];
void init(){memset(s, 0, sizeof(s));}
};
int n, m, mod;
int ksc(ll a, ll b, ll p){
ll t = a * b - (ll)((long double)a * b / p + 0.5) * p;
t = (t < 0)? t + p : t;
return (int)t;
}
inline Mat mul(Mat a, Mat b){
Mat c;
c.init();
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
for(int k = 0; k < m; k++){
c.s[i][j] = (c.s[i][j] + ksc(a.s[i][k], b.s[k][j], mod)) % mod;
}
}
}
return c;
}
Mat pre[maxn], suf[maxn], a[maxn];
int cnt1, cnt2, c[maxn];
void ins(Mat x){
if(cnt1 == 0) pre[++cnt1] = x;
else{
pre[++cnt1] = x;
pre[cnt1] = mul(pre[cnt1 - 1], x);
}
a[cnt1] = x;
}
void del(){
if(cnt2 == 0){
for(int i = cnt1; i >= 1; i--){
if(cnt2 == 0) suf[++cnt2] = a[i];
else suf[++cnt2] = a[i], suf[cnt2] = mul(suf[cnt2], suf[cnt2 - 1]);
}
cnt1 = 0;
}
cnt2--;
}
int main(){
while(~scanf("%d%d%d", &n, &m, &mod)){
cnt1 = cnt2 = 0;
Mat A, B, ret;
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
scanf("%d", &A.s[i][j]);
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
scanf("%d", &B.s[i][j]);
}
}
for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
int L = 0;
ins(A);
for(int i = 1; i <= n; i++){
while(L < c[i]) del(), L++;
if(cnt1 && cnt2) ret = mul(suf[cnt2], pre[cnt1]);
else if(cnt1) ret = pre[cnt1];
else ret = suf[cnt2];
ret = mul(ret, B);
ins(ret);
}
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
printf("%d%c", ret.s[i][j], j == m - 1? '\n' : ' ');
}
}
}
return 0;
}