VOJ 1049送给圣诞夜的礼物——矩阵快速幂模板

题意

顺次给出 $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' : ' ');

}

参考链接：

1. 十个利用矩阵乘法解决的经典问题——Matrix67

2. https://www.cnblogs.com/zhchoutai/p/6789494.html

巴特西

VOJ 1049送给圣诞夜的礼物——矩阵快速幂模板

题意

分析

最新文章

热门文章