poj 3735 Training little cats

点击打开poj 3735

思路: 矩阵快速幂

分析:

1 题目给定n只猫，每只猫的初始的花生的数量为0。现在有三种操作，g i 第i只猫加一个花生，e i 把第i只猫的所有花生全部吃完 s i j 把第i 和 j只猫的花生数进行交换

2 根据上面的三种操作那么我们能够举例n = 3的时候的三种操作。

   对于g 1，我们把第一行的最后一位加1，这里增加了一列目的是为了能够求出和，因为初始化a b c都为0 

   1 0 0 1       a        a+1

   0 1 0 0   *  b   =   b

   0 0 1 0       c         c

   0 0 0 1       1         1

   对于e 1，我们把第一行全部置为0，那么这样就是相当于吃掉全部的花生

   0 0 0 0       a        0

   0 1 0 0   *  b   =   b

   0 0 1 0       c         c

   0 0 0 1       1         1

   对于 s 1 2 

   0 1 0 0       a        b

   1 0 0 0   *  b   =   a

   0 0 1 0       c         c

   0 0 0 1       1         1

3 那么我们只要先把k次的操作整合到一个矩阵A里面，然后求A^m，矩阵的最后一列的前n个数即为所求

4 由于矩阵乘法涉及到乘的次数越多，就越耗时间，因此我们需要在矩阵相乘的时候进行优化

代码:

/************************************************
 * By: chenguolin                               *
 * Date: 2013-08-31                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int N = 105;

int n , m , k;
struct Matrix{
    int64 mat[N][N];
    Matrix operator*(const Matrix& ma)const{
        Matrix tmp;
        for(int i = 0 ; i <= n ; i++){
            for(int j = 0 ; j <= n ; j++){
                tmp.mat[i][j] = 0;
                for(int k = 0 ; k <= n ; k++){
                    if(mat[i][k] && ma.mat[k][j])
                       tmp.mat[i][j] += mat[i][k]*ma.mat[k][j];
                }
            }
        }
        return tmp;
    }
};

void input(Matrix &ma){
    char c;
    int x , y;
    memset(ma.mat , 0 , sizeof(ma.mat));
    for(int i = 0 ; i <= n ; i++)
        ma.mat[i][i] = 1;
    while(k--){
         scanf("%c" , &c);
         if(c == 'g'){
             scanf("%d%*c" , &x);
             x--;
             ma.mat[x][n]++;
         }
         else if(c == 's'){
             scanf("%d%d%*c" , &x , &y);
             x-- , y--;
             for(int i = 0 ; i <= n ; i++){
                 int tmp = ma.mat[x][i];
                 ma.mat[x][i] = ma.mat[y][i];
                 ma.mat[y][i] = tmp;
             }
         }
         else{
             scanf("%d%*c" , &x);
             x--;
             for(int i = 0 ; i <= n ; i++)
                 ma.mat[x][i] = 0;
         }
    }
}

void Pow(Matrix &ma){
    Matrix ans;
    memset(ans.mat , 0 , sizeof(ans.mat));
    for(int i = 0 ; i <= n ; i++)
        ans.mat[i][i] = 1;
    while(m){
        if(m&1)
            ans = ans*ma;
        m >>= 1;
        ma = ma*ma;
    }
    for(int i = 0 ; i < n ; i++){
        if(i) printf(" ");
        printf("%lld" , ans.mat[i][n]);
    }
    puts("");
}

int main(){
    Matrix ma;
    while(scanf("%d%d%d%*c" , &n , &m , &k) && n+m+k){
        input(ma);
        Pow(ma);
    }
    return 0;
}