結果

問題 No.2394 部分和乗総和
コンテスト
ユーザー InTheBloom
提出日時 2023-08-04 21:05:19
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 158 ms / 2,000 ms
コード長 1,333 bytes
コンパイル時間 5,400 ms
コンパイル使用メモリ 213,028 KB
実行使用メモリ 10,788 KB
最終ジャッジ日時 2024-10-14 18:49:26
合計ジャッジ時間 7,445 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    int N, B;
    long M;
    readf("%d %d %d ", N, M, B);
    long[] A = readln.split.to!(long[]);
    solve(N, M, B, A);
}

void solve (int N, long M, int B, long[] A) {
    // dp[i] := 数列Aの前からi個をもちいて取れる部分列すべてに対して、M^s(A[0..i]) の和
    long[] dp = new long[](N+1);

    // initialize
    dp[0] = 1 % B; // 空集合

    // 取る or 取らない で全通り列挙
    // M^s1 + M^s2 + M^s3 + ... + M^sN -> (同じもの)  +  M^(s1+A[i]) + M^(s2+A[i]) + M^(s3+A[i]) + ... + M^(sN+A[i])
    // 指数法則から、和を積に解せて、これをまとめてあげる

    foreach (i; 0..N) {
        dp[i+1] = dp[i] * (1 + modPow(M, A[i], B)); dp[i+1] %= B;
    }

    writeln(dp[N]);
}

long modPow (long a, long x, const int MOD) {
    // assertion
    assert(0 <= x);
    assert(1 <= MOD);

    // normalize
    a %= MOD; a += MOD; a %= MOD;

    // simple case
    if (MOD == 1) {
        return 0L;
    }

    if (x == 0) {
        return 1L;
    }

    if (x == 1) {
        return a;
    }

    // calculate
    long res = 1L;
    long base = a % MOD;
    while (x != 0) {
        if ((x&1) != 0) {
            res *= base;
            res %= MOD;
        }
        base = base*base; base %= MOD;
        x >>= 1;
    }

    return res;
}
0