题意
顺次给出 $m$个置换,反复使用这 $m$ 个置换对一个长为 $n$ 初始序列进行操作,问 $k$ 次置换后的序列。$m<=10, k<2^31$。
分析
对序列的置换可表示成乘上一个矩阵,例如
$$\begin{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}
\times \begin{bmatrix} 1\\ 2\\ 3\\ 4\\ 5\\ 6\\ 7 \end{bmatrix}
= \begin{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[][];
matrix(){
memset(mat, , 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 = ;i < A.r;i++)
for(int k = ;k < A.c;k++)
for(int j = ;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 = ;i < ret.r;i++) ret.mat[i][i] = ;
while(n)
{
if(n & ) ret = mul(ret, A);
A = mul(A, A);
n >>= ;
}
return ret;
} int main()
{
scanf("%d%d%d", &n, &m, &k);
matrix A;
A.r = A.c = n;
for(int i = ;i < n;i++) A.mat[i][i] = ;
int t = k % m;
matrix yu; yu.r = yu.c = n;
for(int i = ;i < m;i++)
{
if(i == t) yu = A; //记录剩余部分的乘积 matrix tmp; tmp.r = tmp.c = n;
for(int j = ;j < n;j++)
{
int x;
scanf("%d", &x);
tmp.mat[j][x-] = ;
}
A = mul(tmp, A);
}
A = mpow(A, k/m);
A = mul(yu, A); //注意顺序,矩阵乘法不满足交换律 for(int i = ;i < n;i++)
for(int j = ;j < n;j++)
if(A.mat[i][j]) printf("%d%c", j+, i == n- ? '\n' : ' ');
}
参考链接: