题意
顺次给出 $m$个置换，反复使用这 $m$ 个置换对一个长为 $n$ 初始序列进行操作，问 $k$ 次置换后的序列。$m<=10, k<2^31$。
分析
对序列的置换可表示成乘上一个矩阵，例如
$$egin{bmatrix}
0 & 0 & 0& 0 & 0 & 1 & 0\
1 & 0 & 0 & 0 & 0 & 0 & 0\
0 & 0 & 1 & 0 & 0 & 0 & 0\
0 & 0 & 0 & 0 & 0 & 0 & 1\
0 & 0 & 0 & 0 & 1 &0 &0 \
0 & 1 & 0 & 0 & 0 & 0 & 0\
0 & 0 & 0 & 1 & 0 &0 & 0
end{bmatrix}
imes egin{bmatrix} 1\ 2\ 3\ 4\ 5\ 6\ 7 end{bmatrix}
= egin{bmatrix} 6\ 1\ 3\ 7\ 5\ 2\ 4 end{bmatrix}$$
因此，只需要将 $m$ 个“置换”乘起来，然后执行 $k/m$ 次，剩下的 $k \% m$ 次模拟一下。
#include<cstdio> #include<cstring> using namespace std; typedef long long ll; struct matrix { int r, c; int mat[105][105]; matrix(){ memset(mat, 0, sizeof(mat)); } }; int n, m, k; matrix mul(matrix A, matrix B) //矩阵相乘 { matrix ret; ret.r = A.r; ret.c = B.c; for(int i = 0;i < A.r;i++) for(int k = 0;k < A.c;k++) for(int j = 0;j < B.c;j++) { ret.mat[i][j] = (ret.mat[i][j] + A.mat[i][k] * B.mat[k][j]); } return ret; } matrix mpow(matrix A, int n) { matrix ret; ret.r = A.r; ret.c = A.c; for(int i = 0;i < ret.r;i++) ret.mat[i][i] = 1; while(n) { if(n & 1) ret = mul(ret, A); A = mul(A, A); n >>= 1; } return ret; } int main() { scanf("%d%d%d", &n, &m, &k); matrix A; A.r = A.c = n; for(int i = 0;i < n;i++) A.mat[i][i] = 1; int t = k % m; matrix yu; yu.r = yu.c = n; for(int i = 0;i < m;i++) { if(i == t) yu = A; //记录剩余部分的乘积 matrix tmp; tmp.r = tmp.c = n; for(int j = 0;j < n;j++) { int x; scanf("%d", &x); tmp.mat[j][x-1] = 1; } A = mul(tmp, A); } A = mpow(A, k/m); A = mul(yu, A); //注意顺序，矩阵乘法不满足交换律 for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) if(A.mat[i][j]) printf("%d%c", j+1, i == n-1 ? ' ' : ' '); }
参考链接：