結果

問題 No.2394 部分和乗総和
ユーザー InTheBloomInTheBloom
提出日時 2023-08-04 21:04:19
言語 D
(dmd 2.106.1)
結果
RE  
実行時間 -
コード長 1,330 bytes
コンパイル時間 6,643 ms
コンパイル使用メモリ 209,920 KB
実行使用メモリ 7,600 KB
最終ジャッジ日時 2024-04-22 19:15:27
合計ジャッジ時間 7,767 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 4 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

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

void solve (int N, long M, int B, int[] 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