#896082 (C++17) No.2394 部分和乗総和

• 問題: No.2394 部分和乗総和
• ユーザー: kobaryo222
• 提出日時: 2023-07-28 21:49:24
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 73 ms / 2,000 ms
• コード長: 6,317 bytes
• コンパイル時間: 2,566 ms
• コンパイル使用メモリ: 198,332 KB
• 最終ジャッジ日時: 2025-02-15 20:14:41
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
other	AC * 21

ソースコード

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define vm vector<mint>
#define vvm vector<vector<mint>>
#define vvvm vector<vector<vector<mint>>>
#define vp vector<pl>
#define vvp vector<vector<pl>>
#define vs vector<string>
#define vvs vector<vector<string>>
#define vb vector<bool>
#define vvb vector<vb>
#define vvvb vector<vvb>

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(ll i = ll(a); i < ll(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(x) std::begin(x), std::end(x)
#define make_unique(v) v.erase(unique(all(v)), v.end());
#define sum(...) accumulate(all(__VA_ARGS__), 0LL)
#define inf (0x1fffffffffffffffLL)

template <class T>
istream &operator>>(istream &is, vector<T> &v) {
    for(auto &x : v) {
        is >> x;
    }
    return is;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for(int i = 0; i < (int)v.size(); i++) {
        if(i != (int)v.size() - 1)
            os << v[i] << " ";
        else
            os << v[i];
    }
    return os;
}

template <typename T, typename... Args>
auto make_v(T x, int arg, Args... args) {
    if constexpr(sizeof...(args) == 0)
        return vector<T>(arg, x);
    else
        return vector(arg, make_v<T>(x, args...));
}

template <class T>
auto min(const T &a) {
    return *min_element(all(a));
}

template <class T>
auto max(const T &a) {
    return *max_element(all(a));
}

template <class T>
bool chmin(T &a, const T &b) {
    return a > b ? a = b, true : false;
}

template <class T>
bool chmax(T &a, const T &b) {
    return a < b ? a = b, true : false;
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;
#line 2 "modint/arbitrary-modint.hpp"

#line 2 "modint/barrett-reduction.hpp"

#include <utility>
using namespace std;

struct Barrett {
    using u32 = unsigned int;
    using i64 = long long;
    using u64 = unsigned long long;
    u32 m;
    u64 im;
    Barrett()
      : m(), im() {}
    Barrett(int n)
      : m(n), im(u64(-1) / m + 1) {}
    constexpr inline i64 quo(u64 n) {
        u64 x = u64((__uint128_t(n) * im) >> 64);
        u32 r = n - x * m;
        return m <= r ? x - 1 : x;
    }
    constexpr inline i64 rem(u64 n) {
        u64 x = u64((__uint128_t(n) * im) >> 64);
        u32 r = n - x * m;
        return m <= r ? r + m : r;
    }
    constexpr inline pair<i64, int> quorem(u64 n) {
        u64 x = u64((__uint128_t(n) * im) >> 64);
        u32 r = n - x * m;
        if(m <= r) return {x - 1, r + m};
        return {x, r};
    }
    constexpr inline i64 pow(u64 n, i64 p) {
        u32 a = rem(n), r = m == 1 ? 0 : 1;
        while(p) {
            if(p & 1) r = rem(u64(r) * a);
            a = rem(u64(a) * a);
            p >>= 1;
        }
        return r;
    }
};
#line 4 "modint/arbitrary-modint.hpp"

template <int id>
struct ArbitraryModIntBase {
    int x;

    ArbitraryModIntBase()
      : x(0) {}

    ArbitraryModIntBase(int64_t y) {
        int z = y % get_mod();
        if(z < 0) z += get_mod();
        x = z;
    }

    ArbitraryModIntBase &operator+=(const ArbitraryModIntBase &p) {
        if((x += p.x) >= get_mod()) x -= get_mod();
        return *this;
    }

    ArbitraryModIntBase &operator-=(const ArbitraryModIntBase &p) {
        if((x += get_mod() - p.x) >= get_mod()) x -= get_mod();
        return *this;
    }

    ArbitraryModIntBase &operator*=(const ArbitraryModIntBase &p) {
        x = rem((unsigned long long)x * p.x);
        return *this;
    }

    ArbitraryModIntBase &operator/=(const ArbitraryModIntBase &p) {
        *this *= p.inverse();
        return *this;
    }

    ArbitraryModIntBase operator-() const { return ArbitraryModIntBase(-x); }
    ArbitraryModIntBase operator+() const { return *this; }

    ArbitraryModIntBase operator+(const ArbitraryModIntBase &p) const {
        return ArbitraryModIntBase(*this) += p;
    }

    ArbitraryModIntBase operator-(const ArbitraryModIntBase &p) const {
        return ArbitraryModIntBase(*this) -= p;
    }

    ArbitraryModIntBase operator*(const ArbitraryModIntBase &p) const {
        return ArbitraryModIntBase(*this) *= p;
    }

    ArbitraryModIntBase operator/(const ArbitraryModIntBase &p) const {
        return ArbitraryModIntBase(*this) /= p;
    }

    bool operator==(const ArbitraryModIntBase &p) const { return x == p.x; }

    bool operator!=(const ArbitraryModIntBase &p) const { return x != p.x; }

    ArbitraryModIntBase inverse() const {
        int a = x, b = get_mod(), u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ArbitraryModIntBase(u);
    }

    ArbitraryModIntBase pow(int64_t n) const {
        ArbitraryModIntBase ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ArbitraryModIntBase &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ArbitraryModIntBase &a) {
        int64_t t;
        is >> t;
        a = ArbitraryModIntBase(t);
        return (is);
    }

    int get() const { return x; }

    inline unsigned int rem(unsigned long long p) { return barrett().rem(p); }

    static inline Barrett &barrett() {
        static Barrett b;
        return b;
    }

    static inline int &get_mod() {
        static int mod = 0;
        return mod;
    }

    static void set_mod(int md) {
        assert(0 < md && md <= (1LL << 30) - 1);
        get_mod() = md;
        barrett() = Barrett(md);
    }
};

using ArbitraryModInt = ArbitraryModIntBase<-1>;

/**
 * @brief modint (2^{30} 未満の任意 mod 用)
 */
int main() {
    ll N, M, B;
    cin >> N >> M >> B;
    vl A(N);
    cin >> A;
    using mint = ArbitraryModInt;
    mint().set_mod(B);
    mint ans = 1;
    rep(i, N){
        ans = ans + ans * mint(M).pow(A[i]);
    }
    cout << ans << endl;
}