結果

問題 No.1025 Modular Equation
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:00:37
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 865 bytes
コンパイル時間 444 ms
コンパイル使用メモリ 82,672 KB
実行使用メモリ 525,172 KB
最終ジャッジ日時 2025-06-12 14:01:51
合計ジャッジ時間 8,412 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 MLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

p, n, k, b = map(int, input().split())
a = list(map(int, input().split()))

zeros = sum(1 for x in a if x == 0)
non_zeros = [x for x in a if x != 0]

# Precompute frequency lists for each non-zero a_i
freq_list = []
for ai in non_zeros:
    freq = {}
    for x in range(p):
        s = pow(x, k, p)
        contrib = (ai * s) % p
        if contrib in freq:
            freq[contrib] += 1
        else:
            freq[contrib] = 1
    freq_list.append(list(freq.items()))

# Initialize DP
dp = [0] * p
dp[0] = 1

for freq in freq_list:
    new_dp = [0] * p
    for s in range(p):
        if dp[s] == 0:
            continue
        for (v, cnt) in freq:
            new_s = (s + v) % p
            new_dp[new_s] = (new_dp[new_s] + dp[s] * cnt) % MOD
    dp = new_dp

# Multiply by p^zeros
result = (dp[b] * pow(p, zeros, MOD)) % MOD
print(result)
0