結果
問題 | No.2394 部分和乗総和 |
ユーザー |
|
提出日時 | 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 |
ソースコード
typedef long long ll;typedef long double ld;#include <bits/stdc++.h>using namespace std;#define int long longll isqrt(ll N){ll sqrtN=sqrt(N)-1;while(sqrtN+1<=N/(sqrtN+1))sqrtN++;return sqrtN;}// modintstruct Fp {// static menberstatic int MOD;// inner valuelong long val;// constructorFp() : 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 operatorsFp 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 operatorsbool 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;}