POJ 3735 Training little cats
不知道为什么RE
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
struct matrix{
ll h,l;
ll num[110][110];
void MatrixInit(ll val){
memset(num,0,sizeof(val));
}
matrix operator +(const matrix &b) const{
matrix res;
res.h = h;
res.l = b.l;
res.MatrixInit(0);
for(ll i = 1; i <= res.h; i++){
for(ll j = 1; j <= res.l; j++){
res.num[i][j]=num[i][j]+b.num[i][j];
}
}
return res;
}
matrix operator *(const matrix &b) const{
matrix res;
res.h = h;
res.l = b.l;
res.MatrixInit(0);
for(ll i = 1; i <= res.h; i++){
for(ll j = 1; j <= res.l; j++){
for(ll k = 1; k <= l; k++){
res.num[i][j]+=(num[i][k]*b.num[k][j]);
}
}
}
return res;
}
};
matrix MFP(matrix u,ll b){
if(b==1) return u;
matrix t = MFP(u,b>>1);
t = t*t;
if(b&1) return (u*t);
return t;
}
int main(){
while(1){
ll n,k,m;
scanf("%lld%lld%lld",&n,&m,&k);
//cout << n << m << k << endl;
if(n==0&&m==0&&k==0){
return 0;
}
matrix ans;
ans.h = n+1;
ans.l = 1;
ans.MatrixInit(0);
ans.num[n+1][1] = 1;
matrix base;
base.h = n+1;
base.l = n+1;
for(ll i = 1; i <= n+1; i++){
base.num[i][i] = 1;
}
for(int j = 1; j <= k; j++){
//printf("--------------\nj = %d\n",j);
char op;
ll x,y;
cin >> op >> x;
//cout << op << ":" << x << endl;
//cout << op << endl;
if(op=='g'){
//printf("[*]|g|:%lld\n",x);
base.num[x][n+1]++;
} else if(op=='e'){
for(ll i = 1; i <= n+1; i++) base.num[x][i] = 0;
} else {
cin >> y;
for(ll i = 1; i <= n+1; i++){
ll tmp = base.num[x][i];
base.num[x][i] = base.num[y][i];
base.num[y][i] = tmp;
}
}
//printf("%c--%lld\n",op,x);
//printf("YEAH\n");
}
base = MFP(base,m);
ans = base*ans;
for(ll i = 1; i <= n; i++) printf("%lld ",ans.num[i][1]);
puts("");
}
return 0;
}