kmjp's blog

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

CSAcademy Round #37 : E. Recursive Arrays

方針あってたのにツメが甘かった。
https://csacademy.com/contest/round-37/task/recursive-arrays/

問題

N要素の数列A[i]が与えられる。
A[i] ← A[A[i]]という代入作業を繰り返すとき、Aは何通り現れるか。

解法

i→A[i]に辺を張った有向グラフを考える。
各頂点iから、1,2,4,...,2^k,...回辺をたどって現れる頂点集合を求める問題になる。
この形状のグラフは辺をたどるといずれ閉路に落ち込むため、辺をたどる回数を倍々していくことに対し、いずれ周期的になることがわかる。

よって個々の閉路に関し周期性を求め、その最大公約数を考えると、全体の周期がわかる。
また、その値に対し、周期的な動作に入るまでの遷移回数を加算したものが解となる。
周期的動作に入るまでの遷移回数は各頂点における下記値の最大値である。

  • 頂点iがすでに閉路内にある場合、閉路長が2^k*pである場合(pは奇数)、最初k回の遷移まではその後の周期的動作に現れない値が現れる。
  • 頂点iが閉路外にある場合、閉路までの距離が(2^k-1)以下となる最大のkに対し、最初k回の遷移まではその後の周期的動作に現れない値が現れる。

あとはグラフを強連結成分分解して上記kをそれぞれ求めよう。

ll mo=1000000007;

map<ll,int> enumpr(ll n) {
	map<ll,int> V;
	for(ll i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
	if(n>1) V[n]++;
	return V;
}

class SCC {
public:
	static const int MV = 120000;
	vector<vector<int> > SC; int NV,GR[MV],rev[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu); rev[cu]=ind;
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0; SC.clear(); SC.resize(MV); NUM.clear();
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};

SCC sc;
int N;
int A[101010];
int inloop[101010];
int dist[101010];

void dfs(int cur) {
	if(inloop[cur]) return;
	dfs(A[cur]);
	inloop[cur]=inloop[A[cur]];
	dist[cur]=dist[A[cur]]+1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	sc.init(N);
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		if(i==A[i]) inloop[i]=1;
		else sc.add_edge(i,A[i]);
	}
	
	sc.scc();
	FOR(i,sc.SC.size()) if(sc.SC[i].size()>1) {
		FOR(j,sc.SC[i].size()) inloop[sc.SC[i][j]]=sc.SC[i].size();
	}
	
	int mad=0;
	set<int> lp;
	FOR(i,N) {
		dfs(i);
		lp.insert(inloop[i]);
		mad=max(mad,dist[i]);
	}
	
	int first=0;
	mad=max(0,mad-1);
	while(mad) mad/=2, first++;
	map<int,int> lcm;
	
	FORR(r,lp) {
		int v=r;
		int step=0;
		while(v%2==0) step++,v/=2;
		first=max(first,step);
		
		if(v==1) continue;
		
		step=1;
		int cur=2%v;
		while(cur!=1) {
			cur=cur*2%v;
			step++;
		}
		
		auto M=enumpr(step);
		FORR(e,M) lcm[e.first]=max(lcm[e.first],e.second);
	}
	ll ret=1;
	FORR(e,lcm) {
		FOR(i,e.second) (ret*=e.first)%=mo;
	}
	cout<<(ret+first)%mo<<endl;
	
	
}

まとめ

シンプルな問題ながら、細かなテクをいろいろ使う感じなのが面白い。