제출 #1064591

#제출 시각아이디문제언어결과실행 시간메모리
1064591BoomydayTrains (BOI24_trains)C++17
100 / 100
683 ms364568 KiB
//
// Created by adavy on 8/18/2024.
//
#include <bits/stdc++.h>


using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;

int main(){
     ll N; cin >> N;
     vector<ll> d(N),x(N);
     for(int i=0;i<N;++i){
         cin >> d[i] >> x[i];
     }
     vector<ll> dp(N,1);
     ll B = floor(sqrt(N))+1;
     vector<vector<vector<ll>>> prefs(B); // type, modulo, preflist
     for(int i=0;i<B;++i){
         prefs[i] = vector<vector<ll>>(B,{0});
     }



     for(int i=N-1;i>=0;--i){
         if (d[i] == 0) {}
         else if (d[i] >= B){

             for(int j=i+d[i]; j<=min(N-1, i+x[i]*d[i]);j+=d[i]){
                 dp[i] += dp[j];
                 dp[i] %= MOD;
             }
         }
         else {
             ll psz = prefs[d[i]][i%d[i]].size();

             dp[i] += prefs[d[i]][i%d[i]][psz-1] - prefs[d[i]][i%d[i]][max(0LL,psz-x[i]-1)] + MOD;
             dp[i] %= MOD;

         }
         for(int j=1;j<B;++j){
             prefs[j][i%j].push_back((prefs[j][i%j].back()+dp[i])%MOD);
         }
     }
     cout << dp[0] << endl;



    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...