POJ 3735(矩阵快速幂)

69 阅读 0 评论 46 点赞

我是靠谱客的博主昏睡蜡烛，最近开发中收集的这篇文章主要介绍POJ 3735(矩阵快速幂)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：点击打开链接

题目大意：n只猫，k步操作，循环进行m次这k步操作，问你最后每只猫各有几个m花生。其中g i表示给第i只猫一个花生，e i表示把第i只猫的花生全抢了，s i j表示把第i只猫的花生跟第j只猫的花生换一下。

题目思路：选拔赛的时候还以为是什么奇葩思维题..幸好当时没吊死在这道题上...这道题其实是用到了矩阵快速幂

矩阵快速幂：

矩阵快速幂其实主体就用了个快速幂，只不过多了个矩阵乘法(multiply函数)。其中需要先将n++，构造一个猫的数量+1为边长的矩阵，比如3只猫就4*4的矩阵，因为还需要一列来放答案，最后答案正好在最后一列里。如果g就直接m[x][n]++，把这一行最后一列++，如果是e，那就把那行清空，如果是s，就把两行互换。

以下是代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define MAXN 105
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
int n;
struct matrix{
    ll m[MAXN][MAXN];
}a;
char s[5];
matrix multiply(matrix x,matrix y){
    matrix ans;
    memset(ans.m,0,sizeof(ans.m));
    rep(i,1,n){
        rep(j,1,n){
            if(x.m[i][j]){
                rep(k,1,n){
                    ans.m[i][k]=ans.m[i][k]+x.m[i][j]*y.m[j][k];
                }
            }
        }
    }
    return ans;
}
int main(){
    ll m;
    int k,x,y;
    while(~scanf("%d%lld%d",&n,&m,&k)&&(n+m+k)){
        n++;
        memset(a.m,0,sizeof(a.m));
        rep(i,1,n){
            a.m[i][i]=1;
        }
        rep(i,1,k){
            scanf("%s",s);
            if(s[0]=='g'){
                scanf("%d",&x);
                a.m[x][n]++;
            }
            if(s[0]=='e'){
                scanf("%d",&x);
                rep(j,1,n){
                    a.m[x][j]=0;
                }
            }
            if(s[0]=='s'){
                scanf("%d%d",&x,&y);
                rep(j,1,n){
                    ll temp=a.m[x][j];
                    a.m[x][j]=a.m[y][j];
                    a.m[y][j]=temp;
                }
            }
        }
        matrix ans;
        memset(ans.m,0,sizeof(ans.m));
        rep(i,1,n){
            ans.m[i][i]=1;
        }
        while(m){
            if(m&1){
                ans=multiply(ans,a);
            }
            m>>=1;
            a=multiply(a,a);
        }
        rep(i,1,n-1){
            printf("%lld%c",ans.m[i][n],i==n-1?'n':' ');
        }
    }
    return 0;
}