E - Putting Candies

問題

長さ の数列が与えられる。以下の操作を回繰り返す。
・ 最初の数をとする。　に を追加する。
を答えよ

解法

愚直にシミュレーションするのは自明にTLEとなる。
よく考えると、追加されるのはで割ったあまりを添え字とする数列である。この数は、たかだか個である。
重要な考察として、の値は常に増えていくが追加される数はの番目である。つまり、 の追加によって増える増加分を一度記録しておけば、後はそれを使い回すだけで良い。
鳩の巣原理ja.wikipedia.org

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

using Int = long long;

int main() {
    Int N,K;
    cin >> N >> K;
    
    vector<Int>A(N);
    map<Int,Int> visit, pans;
    
    for(auto& e  : A)
        cin >> e;
    
    Int ans = 0;
    
    for(Int i  = 0; i < K; ++i){
        Int mod = (ans % N);
        Int elm = A[mod];
        ans += elm;
        pans[i] = ans;
        
        if(visit.find(mod) != visit.end()){
            
            Int prev = visit[mod];
            Int T = i - prev;
            Int csum = ans - pans[prev], remain = K - i - 1;
            
            ans += (csum) * (remain / T);
            
            for(int j = 0; j < remain % T; ++j){
                mod = (ans % N);
                ans += A[mod];
            }
            break;
        }
        
        visit[mod] = i;
        
    }
    
    cout << ans << endl;
}