結果

問題 No.1025 Modular Equation
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:04:42
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,293 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 82,064 KB
実行使用メモリ 848,748 KB
最終ジャッジ日時 2025-06-12 19:05:39
合計ジャッジ時間 7,243 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 MLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

MOD = 10**9 + 7

def main():
    p, n, k, b = map(int, sys.stdin.readline().split())
    a_list = list(map(int, sys.stdin.readline().split()))
    
    d = math.gcd(k, p-1)
    
    # Precompute H: residues of x^k mod p for x in 0..p-1
    H = set()
    for x in range(p):
        res = pow(x, k, p)
        H.add(res)
    H = sorted(H)
    
    terms = []
    for ai in a_list:
        if ai == 0:
            terms.append({0: p})
        else:
            freq = {}
            freq[0] = 1  # x=0
            for h in H:
                if h == 0:
                    continue
                c = (ai * h) % p
                if c in freq:
                    freq[c] += d
                else:
                    freq[c] = d
            terms.append(freq)
    
    dp = [0] * p
    dp[0] = 1
    
    for term in terms:
        new_dp = [0] * p
        for s in range(p):
            if 0 in term:
                cnt0 = term[0]
                new_dp[s] = (new_dp[s] + dp[s] * cnt0) % MOD
            for c in term:
                if c == 0:
                    continue
                prev_s = (s - c) % p
                new_dp[s] = (new_dp[s] + dp[prev_s] * term[c]) % MOD
        dp = new_dp
    
    print(dp[b] % MOD)

if __name__ == "__main__":
    main()
0