結果

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

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    p = int(input[ptr]); ptr +=1
    n = int(input[ptr]); ptr +=1
    k = int(input[ptr]); ptr +=1
    b = int(input[ptr]); ptr +=1
    a_list = list(map(int, input[ptr:ptr+n]))
    ptr +=n

    # Precompute x^k mod p for all x in 0..p-1
    pow_x = [pow(x, k, p) for x in range(p)]

    terms = []
    for a in a_list:
        if a == 0:
            terms.append({0: 1})  # but wait, x can be any, so a_i x^k is 0 for all x. So count is p.
            # So freq is {0: p}
            terms[-1] = {0: p % MOD}
            continue
        # Compute the frequency for a * pow_x[x] mod p
        freq = {}
        for x in range(p):
            c = (a * pow_x[x]) % p
            if c in freq:
                freq[c] = (freq[c] + 1) % MOD
            else:
                freq[c] = 1 % MOD
        terms.append(freq)
    
    # Initialize DP
    dp = [0] * p
    dp[0] = 1  # initial sum is 0

    for term in terms:
        next_dp = [0] * p
        # Iterate over all current residues s where dp[s] is non-zero
        for s in range(p):
            if dp[s] == 0:
                continue
            # Iterate over all residues c in the term's frequency
            for c, cnt in term.items():
                new_s = (s + c) % p
                next_dp[new_s] = (next_dp[new_s] + dp[s] * cnt) % MOD
        dp = next_dp

    print(dp[b] % MOD)

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