結果

問題 No.2394 部分和乗総和
ユーザー InTheBloomInTheBloom
提出日時 2023-08-04 21:05:19
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 160 ms / 2,000 ms
コード長 1,333 bytes
コンパイル時間 6,521 ms
コンパイル使用メモリ 211,792 KB
実行使用メモリ 10,452 KB
最終ジャッジ日時 2024-04-22 19:16:12
合計ジャッジ時間 4,421 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 17 ms
6,940 KB
testcase_14 AC 58 ms
6,944 KB
testcase_15 AC 63 ms
6,944 KB
testcase_16 AC 86 ms
6,940 KB
testcase_17 AC 160 ms
10,452 KB
testcase_18 AC 160 ms
10,340 KB
testcase_19 AC 159 ms
9,076 KB
testcase_20 AC 150 ms
10,132 KB
権限があれば一括ダウンロードができます

ソースコード

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