kmjp's blog

競技プログラミング参加記です

VK Cup 2015 Round 3 : C. Idempotent functions

だいぶ前だけど書かないと忘れるから書いてしまおう。
http://codeforces.com/contest/542/problem/C

問題

{1..n}の整数からなる集合に対し関数gが冪等であるとは、x∈{1..n}に対しg(x)∈{1..n}であり、かつg(g(x))=g(x)となるものをいう。
{1..n}から{1..n}に変換する関数fが与えられる。f^n(x)が冪等となるような最小のnを求めよ。

解法

x∈{1..n}に対しfを繰り返し適用していくといずれループに突入する。
各xに対しこのループの周期と、最初にループに入る最小のfの適用回数を求める。
最終的な解は、全xにおけるループ周期の公倍数のうち、全xでループに突入する最小値を求めたものとなる。

int N;
int F[300];
ll fir[300],per[300];
ll ret=1;
ll maf;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) cin>>F[i];
	for(i=1;i<=N;i++) {
		int ind[300]={};
		MINUS(ind);
		x=0;
		y=i;
		ind[i]=0;
		while(1) {
			x++;
			y=F[y];
			if(ind[y]>=0) {
				fir[i]=ind[y];
				per[i]=x-ind[y];
				break;
			}
			ind[y]=x;
		}
		fir[i]=(fir[i]+per[i]-1)/per[i]*per[i];
		maf = max(maf,fir[i]);
		ret = per[i]*(ret/__gcd(ret,per[i]));
	}
	
	ll tmp=ret;
	while(ret<maf) ret+=tmp;
	cout<<ret<<endl;
	
}

まとめ

これは割と典型っぽいかも。