제출 #1324670

#제출 시각아이디문제언어결과실행 시간메모리
1324670lesinhhungTrains (BOI24_trains)C++20
100 / 100
134 ms41276 KiB
#include <bits/stdc++.h>

using namespace std;

using lint = long long;

const int MOD = 1000000007;

struct mint {
    int val;
    mint() : val(0) {}
    mint(lint v) {
        v %= MOD;
        if (v < 0) v += MOD;
        val = (int)v;
    }

    mint operator-() const { return mint(-val); }

    mint& operator+=(const mint& other) {
        val += other.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    mint& operator-=(const mint& other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }
    mint& operator*=(const mint& other) {
        val = (int)((lint)val * other.val % MOD);
        return *this;
    }

    static mint ipow(mint a, lint p) {
        mint ans(1);
        while (p > 0) {
            if (p & 1) ans *= a;
            a *= a;
            p >>= 1;
        }
        return ans;
    }
    mint inv() const { return ipow(*this, MOD - 2); }

    mint& operator/=(const mint& other) { return (*this) *= other.inv(); }

    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }

    friend ostream& operator<<(ostream& os, const mint& m) {
        return os << m.val;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<array<int, 2>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
    }

    vector<mint> dp(n);
    vector<vector<mint>> sums(100, vector<mint>(n, mint(0)));

    for (int i = n - 1; i >= 0; i--) {
        dp[i] = mint(1);

        int step = a[i][0];
        int cnt  = a[i][1];

        if (step >= 100) {
            for (int j = 1; j <= cnt; j++) {
                long long nxt = (long long)i + 1LL * j * step;
                if (nxt >= n) break;
                dp[i] += dp[(int)nxt];
            }
        } else if (step > 0) {
            int p1 = i + step;
            if (p1 < n) dp[i] += sums[step][p1];

            long long p2 = (long long)i + 1LL * step * (cnt + 1);
            if (p2 < n) dp[i] -= sums[step][(int)p2];
        }

        for (int j = 1; j < 100; j++) {
            mint nextSum = (i + j < n) ? sums[j][i + j] : mint(0);
            sums[j][i] = nextSum + dp[i];
        }
    }
    cout << dp[0];
    
    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...