ZOJ 3563 Alice's Sequence II

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4562

题目：给出一组数列和六种操作， 输出经过P次操作之后的数列。

分析：因为 P (1≤ P ≤ 10⁹)很大，所以直接模拟会超时。也是看了解题报告之后才知道要用矩阵快速幂做。

首先，把操作转化为矩阵乘法。

因为 1×n 的矩阵乘以 n×n 的矩阵还是得到一个 1×n 的矩阵，所以对数列的每一种操作都可以描述成一个n×n 的矩阵。

然后再用矩阵快速幂得结果即可。

快速幂模板：http://www.2cto.com/kf/201207/140412.html

#include <cstdio>
#include <cstring>

const int MAXN = 30;
const int MOD = 10000007;

struct oper_Mat
{
    long long int Mat[MAXN][MAXN];
    friend oper_Mat operator*( oper_Mat &a, oper_Mat&b );
    friend oper_Mat operator^( oper_Mat a, long long int b );
};

oper_Mat OP[12];
oper_Mat initial;
int n;

oper_Mat operator*( oper_Mat &a, oper_Mat &b )   //矩阵乘法
{
    oper_Mat temp;

    memset( temp.Mat, 0, sizeof(temp.Mat) );

    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= n; j++ )
        {
            temp.Mat[i][j] = 0;
            for ( int k = 1; k <= n; k++ )
                temp.Mat[i][j] = (temp.Mat[i][j] + (a.Mat[i][k] * b.Mat[k][j]) % MOD ) % MOD;
        }

    return temp;
}

oper_Mat operator^( oper_Mat a, int k )   //二进制矩阵快速幂
{
    oper_Mat unit;

    memset( unit.Mat, 0, sizeof(unit.Mat) );
    for ( int i = 0; i < MAXN; i++ )
        unit.Mat[i][i] = 1;

    while ( k )
    {
        if ( k&1 ) unit = unit * a;
        a = a * a;
        k >>= 1;
    }

    return unit;
}

void init( int x )             //初始化为单位阵
{
    memset( OP[x].Mat, 0, sizeof(OP[x].Mat) );

    for ( int i = 1; i <= n; i++ )
        OP[x].Mat[i][i] = 1;

    return;
}

void remove( int x )
{
    int i;
    scanf( "%d", &i );

    init(x);

    OP[x].Mat[i][i] = 0;

    return;
}

void Double( int x )
{
    int i;
    scanf( "%d", &i );

    init(x);

    OP[x].Mat[i][i] = 2;

    return;
}

void add( int x )
{
    int i, j;
    scanf( "%d%d", &i, &j );

    init(x);

    if ( i == j )
        OP[x].Mat[i][i] = 2;
    else
        OP[x].Mat[j][i] = 1;

    return;
}

void swap( int x )
{
    int i, j;
    scanf( "%d%d", &i, &j );

    init(x);

    OP[x].Mat[i][i] = 0;
    OP[x].Mat[j][j] = 0;

    OP[x].Mat[i][j] = 1;
    OP[x].Mat[j][i] = 1;

    return;
}

void invert( int x )
{
    int i, j;
    scanf("%d%d", &i, &j);

    init(x);

    for ( int m = i; m <= j; m++ )
        OP[x].Mat[m][m] = 0;

    for ( int m = i, nn = j; m <= j; m++, nn-- )
        OP[x].Mat[ nn ][ m ] = 1;

    return;
}

void transform( int x )
{
    int c, i, d, j;
    scanf( "%d%d%d%d", &c, &i, &d, &j );

    init(x);

    OP[x].Mat[i][i] = c;
    OP[x].Mat[j][i] = d;

    OP[x].Mat[j][j] = 0;

    return;
}

int main()
{
  //  freopen( "out.out", "w", stdout );
    while ( scanf("%d", &n) != EOF )
    {
        for ( int i = 1; i <= n; i++ )
            scanf("%lld", &initial.Mat[1][i]);

        int m;
        scanf( "%d", &m );
        char str[30];
        for ( int i = 1; i <= m; i++ )
        {
            scanf( "%s", str );
            switch( str[0] )
            {
            case 'r' :
                remove(i);
                break;
            case 'd' :
                Double(i);
                break;
            case 'a' :
                add(i);
                break;
            case 's' :
                swap(i);
                break;
            case 'i' :
                invert(i);
                break;
            case 't' :
                transform(i);
                break;
            }
        }

        oper_Mat ans;

        memset( ans.Mat, 0, sizeof(ans.Mat) );
        for ( int i = 0; i < MAXN; i++ )
            ans.Mat[i][i] = 1;

        for ( int i = 1; i <= m; i++ )
            ans = ans * OP[i];

        int step;
        scanf( "%d", &step );

        int k = step / m;
        int Mod = step % m;

        ans = ans ^ k;

        for ( int i = 1; i <= Mod; i++ )
            ans = ans * OP[i];

        ans =initial*ans;

        printf( "%lld", ans.Mat[1][1] );
        for ( int i = 2; i <= n; i++ )
            printf(" %lld", ans.Mat[1][i]);
        putchar('\n');
    }

    return 0;
}