ABC030 D - へんてこ辞書

D - へんてこ辞書

概要

N頂点N辺の有効グラフとN項の数列bが与えられる。各頂点から出る辺は1本であり、b[i]は頂点iから出ている辺を表す。
頂点aからスタートし、k回移動した後にいる頂点番号を答えよ。

制約

2 ≦ N ≦ 10^5
1 ≦ k ≦ 10^100000

共通方針

このグラフにはサイクルがあり、いくらか移動するとそのサイクルをループすることになる。
サイクルのループ開始とループ終了のステップ数を覚えておき、ループ内はmod計算で効率化する。
あとはkの上限10^100000をどのように処理するか。

方針①

多倍長整数のライブラリを使う。もしくはPythonであれば整数型の上限がない（？）ため、多倍長整数を気にする必要がない。

解答①

Submission #5180954 - AtCoder Beginner Contest 030

N, a = map(int, input().split())
k = int(input())
b = list(map(int, input().split()))
 
a -= 1
for i in range(N):
    b[i] -= 1
    
mp = {}
 
st = -1
p = a
cnt = 0
mp[p] = cnt
v = [0] * N
v[cnt] = p
 
while True:
    p = b[p]
    cnt += 1
    
    if p in mp:
        st = mp[p]
        break
        
    mp[p] = cnt
    v[cnt] = p
    
if k < st:
    print(v[k]+1)
else:
    print(v[(k - st) % (cnt - st) + st] + 1)

方針②

多倍長整数のライブラリを使わない方法。
最終的に知りたいのは、kのmodした数値である。
a * b (mod m) = (a mod m) * (b mod m)
a + b (mod m) = (a mod m) + (b mod m)
であることを利用し、文字列になっている数値を1桁ずつ取り出し、modして加算・乗算を行えばよい。

解答②

Submission #5181052 - AtCoder Beginner Contest 030

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, a;
	cin >> N >> a;
	a--;
 
	string k;
	cin >> k;
 
	vector<int> b(N);
	rep(i, N) {
		cin >> b[i];
		b[i]--;
	}
 
	vector<int> v(N);
	map<int, int> mp;
 
	ll st;
	ll p = a;
	ll cnt = 0;
	mp[p] = cnt;
	v[cnt] = p;
	while(true){
		p = b[p];
		cnt++;
 
		auto it = mp.find(p);
		if(it != mp.end()){
			st = mp[p];
			break;
		}
 
		mp[p] = cnt;
		v[cnt] = p;
	}
 
	if(k.size() <= 18){
		ll lk = stoll(k);
		if(lk < st){
			cout << v[lk] + 1 << endl;
		}else{
			cout << v[(lk - st) % (cnt - st) + st]+1 << endl;
		}
	}else{
		ll m = cnt - st;
		ll c = 0;
		ll dig = 1;
		for(int i = k.size()-1; i >= 0; i--){
			c += dig * (k[i] - '0');
			c %= m;
			dig *= 10;
			dig %= m;
		}
		c = (c - st + m * 1000000) % (cnt - st) + st;
		cout << v[c] + 1 << endl;
	}
}