题意：
给你一个1-n的排列\({a_i}\)，一开始排列为1-n，给出一个m行的表，每次要从上到下按照表的每一行重排一次，求重排k次后的排列\({a_i}\)。
题解：
矩阵快速幂；
显然是置换，置换和矩阵乘法有不小的联系，置换一次经常相当于乘一个01矩阵；
于是可以分成初始序列乘上k/i次m行的大矩阵，然后再乘上k%i次小矩阵；
v[i][j]表示第i次操作，第j位上的数字是什么，根据这个构造两个转移矩阵；
前一部分矩阵快速幂，后一部分直接乘一次即可
#include#include #include #include #include #include #define ll long longusing namespace std;int n,m,k,g[105][105],v[105][105],t[105][105];struct Mat { int s[105][105]; void mul(Mat x) { memset(g,0,sizeof(g)); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) for(int k=1; k<=n; k++) g[i][j]+=s[i][k]*x.s[k][j]; memcpy(s,g,sizeof(g)); }}a,b,c,ret;int gi() { int x=0,o=1; char ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}void solve1() { for(int i=1; i<=n; i++) b.s[v[m][i]][i]=1;//first trans ret=b; for(int y=k/m-1; y; y>>=1) {//k/m-1 trans if(y&1) ret.mul(b); b.mul(b); } b=ret;}void solve2() { for(int i=1; i<=n; i++) c.s[v[k%m][i]][i]=1;}int main() { n=gi(),m=gi(),k=gi(); for(int i=1; i<=n; i++) v[0][i]=i; for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { t[i][j]=gi(); v[i][j]=v[i-1][t[i][j]]; } } for(int i=1; i<=n; i++) a.s[1][i]=i; solve1(),solve2(); a.mul(b),a.mul(c); for(int i=1; i<=n; i++) { printf("%d ", a.s[1][i]); } return 0;}