제출 #1330919

#제출 시각아이디문제언어결과실행 시간메모리
1330919lxz20071231Trains (BOI24_trains)C++20
100 / 100
163 ms7672 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long; using db = double; using i128 = __int128_t;
template <class T> using v = vector<T>;
using pii = pair<int, int>; using vi = v<int>; using vpi = v<pii>; using vvi = v<vi>; using vvpi = v<vpi>;
using pll = pair<ll, ll>; using vll = v<ll>; using vpl = v<pll>; using vvl = v<vll>; using vvpl = v<vpl>;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()

const int INF = 1e9;
const ll INFLL = 1e18;

const ll MOD = 1'000'000'007;
const int N = 100005, K=330;
ll n, dp[N], d[N], x[N], dp2[K+5][K+5];
vi out[N];



signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> d[i] >> x[i];
    }

    ll ans = 0;
    dp[1] = 1;

    for (ll i=1; i<=n; i++){
        for (ll j=1; j<=K; j++){
            dp[i] += dp2[j][i % j];
            dp[i] %= MOD;
        }
        if (d[i] > K){
            for (ll j = i+d[i]; j<=min(i+x[i] * d[i], n); j += d[i]){
                dp[j] += dp[i];
                dp[j] %= MOD;
            }
        }
        else if (d[i] > 0){
            ll op = min(n+1, i + x[i] * d[i]);
            out[op].pb(i);
            dp2[d[i]][i % d[i]] += dp[i];
            dp2[d[i]][i % d[i]] %= MOD;
        }

        for (int j : out[i]){
            dp2[d[j]][i % d[j]] -= dp[j];
            dp2[d[j]][i % d[j]] += MOD;
            dp2[d[j]][i % d[j]] %= MOD;
        }
    }

    for (int i=1; i<=n; i++){
        ans += dp[i];
        ans %= MOD;
    }

    cout << ans << '\n';
    
    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...