5480: 孤衾易暖?
描述
哇，好難，我要放棄了(扶我起來，我還能A
寒夜縱長，孤衾易暖，鐘鼓漸清圓。
生活也許有些不如意的地方，但是沒有什么是擁有一只貓不能解決的，我最喜歡蘇格蘭折耳貓。
現在我有n只小貓，我要訓練這些貓去滿足我奇奇怪怪的需求。
就是要讓他們去得到魚，這樣他們才會快樂。剛開始他們是沒有魚的
我對這些貓有3種訓練要求:
第一種要求為get x，意為讓第x只貓咪得到一條；
第二種要求為eat x，意為讓第x只貓咪吃掉它所有的魚；
第三種要求為exchange x y，意為讓第x只貓咪和第y只貓咪交換他們的魚。
人們經常都是復讀機，貓也不例外，你給他們設定某組操作，讓他們重復就好了。
他們需要重復執行某組操作(含有k個要求)m次，求最后它們都有多少只魚。
輸入
?
?
輸入包括多組樣例，讀到文件結尾。
輸入的第一行為三個整數n,m,k，代表有n只貓，要重復的次數m和k個要求組成的操作。
接下來有k行，每一行都有一個訓練方式(m≤1,000,000,000,?n≤100,?k≤100)。
輸出
對于每個樣例都在一行上輸出n個數，代表每只貓有多少只魚。
樣例輸入
3 1 6
get 1
get 2
get 2
exchange 1 2
get 3
eat 2
樣例輸出
?2 0 1
提示
第一只貓得到1條魚，第2只貓得到1條魚，第2只貓得到1條魚，交換1和2的魚數。
第1只貓現在有2條魚，第2只貓現在有1條魚。第三只貓有一條魚，然后第二只貓的魚被吃完。
所以第1只貓現在有2條魚，第2只貓現在有0條魚，第三只貓有1條魚。而且只有一次，故輸出2 0 1。
題目來源
TOJ
?
題目鏈接：http://tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=5480
http://poj.org/problem?id=3735
兩個題目是一樣的，只不過一個英文題面一個中文題目
按照題目要求構造出矩陣，重復的次數用矩陣快速冪計算
對于題目要求的三種操作，可以按照下面的方法構造矩陣
第一種要求為get x，意為讓第x只貓咪得到一條；
即x的位置+1
第二種要求為eat x，意為讓第x只貓咪吃掉它所有的魚；
即x的位置歸0
第三種要求為exchange x y，意為讓第x只貓咪和第y只貓咪交換他們的魚。
即swap(x,y)
?
#include <bits/stdc++.h>
using namespace std;
#define LL __int64
struct A{LL data[111][111];int n;void ini(int nn){//初始化全0矩陣 n=nn;memset(data,0,sizeof(data));}void dw(int nn){//單位矩陣 ini(nn);for(int i=0;i<=n;i++)data[i][i]=1;}A(){n=2;memset(data,0,sizeof(data));}
};
int n;
A operator* (A a,A b)//矩陣乘法，重載乘號
{A ans;for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){if(a.data[i][j]==0)continue;for(int k=0;k<=n;k++){ans.data[i][k]+=a.data[i][j]*b.data[j][k];}}}return ans;
}
A operator^ (A a,int k)//矩陣次冪
{A ans;ans.dw(n);while(k){if(k&1)ans=ans*a;a=a*a;k>>=1;}return ans;
}
int main(){int m,k,x,y;A T;char ch[15];while(~scanf("%d%d%d",&n,&m,&k)){T.dw(n);while(k--){scanf("%s",ch);if(ch[0]=='g'){scanf("%d",&x);T.data[0][x]++;}else if(ch[0]=='e'){if(ch[1]=='x'){scanf("%d %d",&x,&y);for(int i=0;i<=n;i++){swap(T.data[i][x],T.data[i][y]);}}else { scanf("%d",&x);for(int i=0;i<=n;i++){T.data[i][x]=0;}}}}T=T^m;printf("%I64d",T.data[0][1]);for(int i=2;i<=n;i++){printf(" %I64d",T.data[0][i]);}puts("");}
}
?
方式)
