Submission #49103678

---

Source Code Expand

/**
 *  @the_hyp0cr1t3
 *  06.01.2024 18:16
**/
#include <bits/stdc++.h>

template <typename T>
constexpr T pow(T a, long long b) {
    T res{1};
    for (; b; b /= 2, a *= a)
        if (b & 1) res *= a;
    return res;
}

template <int P> struct modint {
    static int mod_;
    int v; // P * 2 may overflow

    constexpr modint() : v{} {}
    constexpr modint(long long u) {
        if (u < 0) u = u % mod() + mod();
        if (u >= mod()) u %= mod();
        v = u;
    }

    constexpr int val() const { return v; }
    constexpr static int mod() {
        if constexpr (P > 0)
            return P;
        else
            return mod_;
    }
    constexpr static void set_mod(int m) {
        mod_ = m;
    }
    explicit constexpr operator int() const { return v; }
    friend constexpr std::istream& operator>>(std::istream& in, modint& m) {
        long long u; in >> u;
        m = modint(u);
        return in;
    }
    friend constexpr std::ostream& operator<<(std::ostream& os, const modint& m) {
        return os << m.v;
    }

    static int inv(int a, int m) {
        int g = m, x = 0, y = 1;
        while (a != 0) {
            int q = g / a;
            g %= a;
            std::swap(g, a);
            x -= q * y;
            std::swap(x, y);
        }
        return x < 0 ? x + m : x;
    }

    constexpr static unsigned fast_mod(uint64_t x, unsigned m = mod()) {
#if !defined(_WIN32) || defined(_WIN64)
        return unsigned(x % m);
#endif  // x must be less than 2^32 * m
        unsigned x_high = unsigned(x >> 32), x_low = unsigned(x), quot, rem;
        asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
        return rem;
    }

    constexpr modint inv() const { return modint(inv(v, mod())); }
    constexpr modint operator-() const { return modint(v ? mod() - v : 0); }
    constexpr modint& operator+=(const modint& o) {
        v += o.v;
        if (v >= mod()) v -= mod();
        return *this;
    }
    constexpr modint& operator-=(const modint& o) {
        v -= o.v;
        if (v < 0) v += mod();
        return *this;
    }
    constexpr modint& operator*=(const modint& o) {
        v = fast_mod(uint64_t(v) * o.v);
        return *this;
    }
    constexpr modint& operator/=(const modint& o) { return *this *= o.inv(); }
    friend constexpr modint operator+(const modint& a, const modint& b) {
        modint res = a; res += b;
        return res;
    }
    friend constexpr modint operator-(const modint& a, const modint& b) {
        modint res = a;
        res -= b;
        return res;
    }
    friend constexpr modint operator*(const modint& a, const modint& b) {
        modint res = a;
        res *= b;
        return res;
    }
    friend constexpr modint operator/(const modint& a, const modint& b) {
        modint res = a;
        res /= b;
        return res;
    }
    friend constexpr bool operator==(const modint& a, const modint& b) {
        return a.val() == b.val();
    }
};

template <>
int modint<0>::mod_ = 1'000'000'007;

constexpr int mod = 998244353;
using Z = modint<mod>;

constexpr int B = 450;
Z add[B][B];

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto &x : a)
        std::cin >> x;

    Z ans = 0;
    std::vector<Z> dp(n);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < B; j++)
            dp[i] += add[j][i % j];

        if (a[i] < B) {
            add[a[i]][i % a[i]] += dp[i];
        } else {
            for (int j = i + a[i]; j < n; j += a[i])
                dp[j] += dp[i];
        }

        ans += dp[i];
    }

    std::cout << ans << '\n';
}

Submission Info

Judge Result