これも定番かな…。
https://yukicoder.me/problems/no/1013
問題
以下原文をだいぶ言い換える。
無限に続く双六があり、各マスには周期Nで数字が書かれている。
1手ごとに現在位置からマス目に書かれた分前に進むとする。
最初のNマスそれぞれから初めてK回移動したとき、どこに到着するか。
解法
まぁこう問題文を言い換えると容易で、ダブリングで2^n回移動したときに何マス進むかわかる。
あとは合計K回移動するようダブリングした結果をlogK個組み合わせればよい。
int N,K; ll P[101010][31]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; FOR(i,N) cin>>P[i][0]; FOR(i,30) { FOR(x,N) { ll y=P[x][i]; ll z=P[(x+y)%N][i]; P[x][i+1]=y+z; } } FOR(i,N) { ll cur=i; for(j=29;j>=0;j--) if(K&(1<<j)) { cur+=P[cur%N][j]; } cout<<cur+1<<endl; } }
まとめ
これは★3でもいいかもね。