PKU 3735 Training little cats
http://poj.org/problem?id=3735
与えられた条件でシミュレーションしろというような問題。
愚直にやると大きいmで絶対に終わらないので、愚直を回避するためになんとかする。
どの操作も行列の掛け算で置き換えることができるので、k回のシミュレーションをまとめて表す行列を作り、繰り返し二乗法を適用しました。
ただし、C++だとどうしてもTLEを回避出来なかったので、javaに逃げさせてもらいました。
それでも結構ギリギリになりました。
0msとなるもっと簡潔な方法があるようなので、それを調べたいです。
import java.util.*; class Main{ public static void main(String[] args){ new Main().run(); } int n,m,k; long mat[][]=new long[110][110]; long tmp[][]=new long[110][110]; long tmp2[][]=new long[110][110]; void matpow(long in[][],int m){ if(m==0){ for(int i=0;i<n+1;++i){ Arrays.fill(in[i],0); in[i][i]=1; } return; } if(m==1)return; if((m&1)==1)for(int i=0;i<n+1;++i)tmp2[i]=(long[])in[i].clone(); matpow(in,m/2); for(int i=0;i<n+1;++i){ for(int j=0;j<n+1;++j){ long t=0; for(int k=0;k<n+1;++k)t+=in[i][k]*in[k][j]; tmp[i][j]=t; } } if((m&1)==1){ for(int i=0;i<n+1;++i){ for(int j=0;j<n+1;++j){ long t=0; for(int k=0;k<n+1;++k)t+=tmp[i][k]*tmp2[k][j]; in[i][j]=t; } } return; } for(int i=0;i<n+1;++i)in[i]=(long[])tmp[i].clone(); } void run(){ Scanner cin=new Scanner(System.in); while(true){ n=cin.nextInt(); m=cin.nextInt(); k=cin.nextInt(); if(0==(n|m|k))break; String c; int s,t; for(int i=0;i<n+1;++i){ Arrays.fill(mat[i],0); mat[i][i]=1; } for(int i=0;i<k;++i){ c=cin.next(); if(c.charAt(0)=='g'){ s=cin.nextInt()-1; ++mat[s][n]; }else if(c.charAt(0)=='e'){ s=cin.nextInt()-1; Arrays.fill(mat[s],0); }else{ s=cin.nextInt()-1; t=cin.nextInt()-1; long[] tt=mat[s]; mat[s]=mat[t]; mat[t]=tt; } } matpow(mat,m); for(int i=0;i<n;++i)System.out.print(mat[i][n]+" "); System.out.println(); } } }