제출 #1330918

#제출 시각아이디문제언어결과실행 시간메모리
1330918lxz20071231Trains (BOI24_trains)C++20
16 / 100
150 ms5712 KiB
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <limits>
#include <functional>
#include <utility>
#include <tuple>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <random>
#include <chrono>
#include <bitset>
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+1][K+1];
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<=i+x[i] * d[i]; 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...