結果

問題 No.2394 部分和乗総和
コンテスト
ユーザー erbowl
提出日時 2023-07-29 07:08:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 168 ms / 2,000 ms
コード長 2,824 bytes
コンパイル時間 1,765 ms
コンパイル使用メモリ 196,096 KB
最終ジャッジ日時 2025-02-15 20:54:26
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

typedef long long ll;
typedef long double ld;

#include <bits/stdc++.h>
using namespace std;
#define int long long

ll isqrt(ll N){
	ll sqrtN=sqrt(N)-1;
	while(sqrtN+1<=N/(sqrtN+1))sqrtN++;
	return sqrtN;
}


// modint
struct Fp {
    // static menber
    static int MOD;
    
    // inner value
    long long val;
    
    // constructor
    Fp() : val(0) { }
    Fp(long long v) : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    long long get() const { return val; }
    static int get_mod() { return MOD; }
    static void set_mod(int mod) { MOD = mod; }
    
    // arithmetic operators
    Fp operator - () const {
        return val ? MOD - val : 0;
    }
    Fp operator + (const Fp &r) const { return Fp(*this) += r; }
    Fp operator - (const Fp &r) const { return Fp(*this) -= r; }
    Fp operator * (const Fp &r) const { return Fp(*this) *= r; }
    Fp operator / (const Fp &r) const { return Fp(*this) /= r; }
    Fp& operator += (const Fp &r) {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    Fp& operator -= (const Fp &r) {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    Fp& operator *= (const Fp &r) {
        val = val * r.val % MOD;
        return *this;
    }
    Fp& operator /= (const Fp &r) {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    Fp pow(long long n) const {
        Fp res(1), mul(*this);
        while (n > 0) {
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    Fp inv() const {
        Fp res(1), div(*this);
        return res / div;
    }

    // other operators
    bool operator == (const Fp &r) const {
        return this->val == r.val;
    }
    bool operator != (const Fp &r) const {
        return this->val != r.val;
    }
    friend istream& operator >> (istream &is, Fp &x) {
        is >> x.val;
        x.val %= x.get_mod();
        if (x.val < 0) x.val += x.get_mod();
        return is;
    }
    friend ostream& operator << (ostream &os, const Fp &x) {
        return os << x.val;
    }
    friend Fp modpow(const Fp &r, long long n) {
        return r.pow(n);
    }
    friend Fp modinv(const Fp &r) {
        return r.inv();
    }
};

int Fp::MOD;


signed main(){
    ll n,m,b;
    std::cin >> n>>m>>b;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    using mint = Fp;
    mint::set_mod(b);

    mint sum = 1;   
    for (int i = 0; i < n; i++) {
        sum = sum + mint(m).pow(a[i])*sum;
    }
    std::cout << sum << std::endl;
}
0