結果

問題 No.2394 部分和乗総和
コンテスト
ユーザー pote-bokko
提出日時 2023-07-30 17:24:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,742 bytes
コンパイル時間 2,119 ms
コンパイル使用メモリ 177,336 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-09 12:35:25
合計ジャッジ時間 5,281 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

// STLのインクルード
#include <bits/stdc++.h>
using namespace std;

// // ACLのインクルード(デフォルトはコメントアウト)
// #include <atcoder/all>
// using namespace atcoder;

// for文の略記
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define per(i, n) for (int i = (int)(n-1); i >= 0; i--)

// vectorのソート
#define all(x) x.begin(), x.end()

// 型の略記 (競プロならでは)
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using vi = vector<int>;
using vl = vector<long long>;
using vs = vector<string>;
using vc = vector<char>;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<long long, long long>>;
using vpsi = vector<pair<string, int>>;
using vvi = vector<vector<int>>;
using vvpii = vector<vector<pair<int, int>>>;
using vvl = vector<vector<long long>>;
using vvc = vector<vector<char>>;

// MOD計算で使う
#define MOD 1000000007
#define MOD2 998244353

// YES-NOで答える質問で使う(fがTrueならYes)
void cout_yn(bool f){
    if(f)cout << "Yes" << endl;
    else cout << "No" << endl;
}

// 木の前順走査
void dfs_preorder(int v, vvi &tree, vi &output){
    output.push_back(v);
    rep(i, tree[v].size()){
        dfs_preorder(tree[v][i], tree, output);
    }
}
// 木の後順走査
void dfs_postorder(int v, vvi &tree, vi &output){
    rep(i, tree[v].size()){
        dfs_preorder(tree[v][i], tree, output);
    }
    output.push_back(v);
}

// n頂点m辺の無向グラフを隣接リストで受け取る.
// 頂点番号は1-indexedとして入力される想定.
vector<vector<int>> input_undir_graph(int n, int m){
    int a, b;
    vector<vector<int>> g(n);
    rep(i, m){
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b); // a->b へ向かう辺
        g[b].push_back(a); // b->a へ向かう辺
    }
    return g;
}

// n頂点m辺の有向グラフを隣接リストで受け取る.
// 頂点番号は1-indexedとして入力される想定.
vector<vector<int>> input_dir_graph(int n, int m){
    int a, b;
    vector<vector<int>> g(n);
    rep(i, m){
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b); // a->b へ向かう辺
    }
    return g;
}

ll modpow(ll x, ll n, ll p) {
  ll ret = 1;
  while(n > 0) {
    if(n & 1) ret = (ret * x) % p;
    x = (x * x) % p;
    n >>= 1;
  }
  return ret;
}

// main関数
int main(void){
    ll n, m, b;
    cin >> n >> m >> b;
    vl a(n);
    rep(i, n)cin >> a[i];
    a.push_back(0);
    sort(all(a));
    vl s(n+1, 1);
    ll ans = 1;
    rep(i, n){
        s[i+1] = s[i] * modpow(m, a[i+1], b) % b + 1;
        ans = (ans + s[i] * modpow(m, a[i+1], b) % b) % b;
    }
    cout << ans << endl;
    return 0;
}
0