提出 #64142162

---

ソースコード 拡げる

#ifdef LOCAL
    #include <bits/include_all.h>
#else
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
#endif

#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int) (x).size())
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll mod = 998244353;
const ll base = 1e6 + 9;
const ll inf = 1e18;
const int MAX = 2e5 + 42;
const int LG = 20;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

constexpr int calculate_phi(int n) {
    if(n == 998244353 || n == 1000000007) return n - 1;
    int ans = n;
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            ans /= i; ans *= i - 1; while(n % i == 0) n /= i;
        }
    }
    if(n > 1) ans /= n, ans *= n - 1;
    return ans;
}

constexpr int phi_minus_one = calculate_phi(mod) - 1;

class Mint {
public:
    int x;

public:
    void norm() {
        x %= mod;
        if(x < 0) x += mod;
    }
    Mint(int a, bool small) {
        x = a;
        if(x >= mod) x -= mod;
        if(x < 0) x += mod;
    }
    Mint() { x = 0; }
    Mint(long long a) {
        if(a >= mod || a <= -mod) a %= mod;
        x = a;
        if(x < 0) x += mod;
    }
    Mint(const Mint &b) { x = b.x; }
    friend ostream &operator <<(ostream &out, const Mint &a) { out << a.x; return out; }
    friend istream &operator >>(istream &in, Mint &a) { in >> a.x; return in; }
    Mint operator +(const Mint &b) const & {
        return Mint(x + b.x, 1);
    }
    Mint operator +(int a) const & {
        return Mint(x + a, 1);
    }
    Mint operator -(const Mint &b) const & {
        return Mint(x - b.x, 1);
    }
    Mint operator -(int a) const & {
        return Mint(x - a, 1);
    }
    friend Mint operator -(const Mint &a) {
        return Mint(mod - a);
    }
    Mint operator *(const Mint &b) const & {
         return Mint(1LL * x * b.x);
    }
    Mint operator *(int a) const & {
        return Mint(1LL * x * a);
    }
    Mint &operator +=(const Mint &b) {
        x += b.x;
        if(x >= mod) x -= mod;
        return *this;
    }
    Mint &operator +=(int a) {
        x += a;
        if(x >= mod) x -= mod;
        return *this;
    }
    Mint &operator -=(const Mint &b) {
        x += mod - b.x;
        if(x >= mod) x -= mod;
        return *this;
    }
    Mint &operator -=(int a) {
        x += mod - a;
        if(x >= mod) x -= mod;
        return *this;
    }
    Mint &operator *=(const Mint &b) {
        x = (long long) x * b.x % mod;
        return *this;
    }
    Mint &operator *=(int a) {
        x = (long long) x * a % mod;
        return *this;
    }
    Mint &operator /=(const Mint &b) {
        x = (long long) x * b.inv().x % mod;
        return *this;
    }
    Mint &operator /=(int a) {
        x = (long long) x * Mint(a, 1).inv().x % mod;
        return *this;
    }
    Mint &operator ++() {
        if(++x == mod) x = 0;
        return *this;
    }
    Mint operator ++(int32_t) {
        Mint ans(*this);
        if(++x == mod) x = 0;
        return ans;
    }
    Mint &operator --() {
        if(--x == -1) x = mod - 1;
        return *this;
    }
    Mint operator --(int32_t) {
        Mint ans(*this);
        if(--x == -1) x = mod - 1;
        return ans;
    }
    Mint bpow(long long n) const & {
        Mint a(x);
        Mint ans(1);
        while(n) {
            if(n & 1) ans *= a;
            n >>= 1;
            a *= a;
        }
        return ans;
    }
    Mint inv() const & {
        return bpow(phi_minus_one);
    }
    Mint operator /(const Mint &b) const & {
        return b.inv() * x;
    }
    Mint operator /(int a) const & {
        return Mint(a, 1).inv() * x;
    }
    friend Mint operator -(int a, const Mint &b) {
        Mint res(b - a);
        res.x = mod - res.x;
        if(res.x == mod) res.x = 0;
        return res;
    }
    friend Mint operator +(int a, const Mint &b) {
        return Mint(b + a);
    }
    friend Mint operator *(int a, const Mint &b) {
        return Mint(b * a);
    }
    friend Mint operator /(int a, const Mint &b) {
        return Mint(a, 1) * b.inv();
    }
    Mint &operator=(const Mint &b) {
        x = b.x;
        return *this;
    }
    bool operator==(int a) const & {
        return (x == a);
    }
    bool operator!=(int a) const & {
        return (x != a);
    }
    bool operator==(const Mint &b) const & {
        return (x == b.x);
    }
    bool operator!=(const Mint &b) const & {
        return (x != b.x);
    }
    friend bool operator==(int a, const Mint &b) {
        return (b.x == a);
    }
    friend bool operator!=(int a, const Mint &b) {
        return (b.x != a);
    }
};

Mint fact[MAX], inv[MAX];

Mint C(int n, int k) {
    if(n < k || k < 0) return 0;
    return fact[n] * inv[k] * inv[n - k];
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 1; i < n; i++) {
        cin >> a[i];
    }

    vector<Mint> pref(n);
    pref[0] = 1;
    for(int i = 1; i < n; i++) pref[i] = 1 + Mint(i).inv();
    for(int i = 1; i < n; i++) pref[i] *= pref[i - 1];
    auto pref_inv = pref;
    for(auto &i : pref_inv) i = i.inv();
    vector<Mint> inv_val(n + 1);
    for(int i = 1; i <= n; i++) inv_val[i] = fact[i - 1] * inv[i];

    Mint sum = 0;
    vector<Mint> precalc(n);
    for(int v = 0; v < n;v++) {
        precalc[v] = sum * fact[n - 1] * pref[v - 1] * pref_inv[0] * inv_val[v] + a[v] * fact[n - 1] * pref[v - 1] * pref_inv[0] * inv_val[v];
        sum += a[v] * inv_val[v + 1];
    }

    auto p_precalc = precalc;
    for(int i = 1; i < n; i++) p_precalc[i] += p_precalc[i - 1];
    p_precalc.insert(p_precalc.begin(), 0);

    vector<Mint> dp(n);
    vector<Mint> pref_dp(n);
    for(int i = 1; i < n; i++) {
        dp[i] += pref_dp[i - 1] * 2 * inv_val[i];
        dp[i] += p_precalc[i] * 2 * inv_val[i];

        pref_dp[i] = pref_dp[i - 1] + dp[i];
    }

    auto calc = [&](int u, int v) -> Mint {
        Mint ans = (u? pref_dp[u - 1] : Mint(0)) * inv_val[u] * inv_val[v] * pref[v - 1] * pref_inv[u];
        ans += p_precalc[u] * inv_val[u] * inv_val[v] * pref[v - 1] * pref_inv[u];

        return ans;
    };

    auto get = [&](int u, int v) -> Mint {
        if(u == v) return 0;
        Mint ans = precalc[u] + precalc[v] - 2 * precalc[u] * pref[v - 1] * pref_inv[u] * inv_val[v];

        ans -= 2 * calc(u, v);

        return ans;
    };

    while(q--) {
        int u, v;
        cin >> u >> v; u--, v--;
        cout << get(u, v) << '\n';
    }
}

signed main() {
    fact[0] = 1; for(int i = 1; i < MAX; i++) fact[i] = fact[i - 1] * i;
    inv[MAX - 1] = 1 / fact[MAX - 1];
    for(int i = MAX - 1; i; i--) inv[i - 1] = inv[i] * i; assert(inv[0] == 1);
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

提出情報

コンパイルエラー

Main.cpp: In constructor ‘Mint::Mint(long long int, bool)’:
Main.cpp:68:22: warning: unused parameter ‘small’ [-Wunused-parameter]
   68 |     Mint(int a, bool small) {
      |                 ~~~~~^~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:285:5: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
  285 |     for(int i = MAX - 1; i; i--) inv[i - 1] = inv[i] * i; assert(inv[0] == 1);
      |     ^~~
In file included from /usr/include/c++/12/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/12/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/12/ext/pb_ds/assoc_container.hpp:48,
                 from Main.cpp:5:
Main.cpp:285:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for’
  285 |     for(int i = MAX - 1; i; i--) inv[i - 1] = inv[i] * i; assert(inv[0] == 1);
      |                                                           ^~~~~~

ジャッジ結果