結果

問題 No.1025 Modular Equation
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:14:41
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,682 bytes
コンパイル時間 491 ms
コンパイル使用メモリ 81,552 KB
実行使用メモリ 667,180 KB
最終ジャッジ日時 2025-04-15 22:16:34
合計ジャッジ時間 10,300 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 MLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import gcd
from collections import defaultdict

MOD = 10**9 + 7

def main():
    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]))
    
    zeros = [a for a in a_list if a == 0]
    m = len(zeros)
    non_zero_a = [a for a in a_list if a != 0]
    ans = pow(p, m, MOD)
    
    if not non_zero_a:
        print(ans if b == 0 else 0)
        return
    
    g = gcd(k, p-1)
    e = (p-1) // g
    
    # Precompute is_kth_residue for d in 1..p-1
    is_kth_residue = [False] * p
    for d in range(1, p):
        if pow(d, e, p) == 1:
            is_kth_residue[d] = True
    
    # Precompute residues for each non-zero a_i
    terms = []
    for a in non_zero_a:
        inv_ai = pow(a, p-2, p)
        residues = []
        for c in range(1, p):
            d = (c * inv_ai) % p
            if d != 0 and is_kth_residue[d]:
                residues.append(c)
        terms.append(residues)
    
    # Initialize DP
    dp = defaultdict(int)
    dp[0] = 1
    
    for residues in terms:
        new_dp = defaultdict(int)
        # Contribution from residue 0 (current_dp remains as is)
        for d, cnt in dp.items():
            new_dp[d] = (new_dp[d] + cnt) % MOD
        # Contribution from non-zero residues
        for c in residues:
            for d, cnt in dp.items():
                new_res = (d + c) % p
                new_dp[new_res] = (new_dp[new_res] + cnt * g) % MOD
        dp = new_dp
    
    print((dp.get(b, 0) * ans) % MOD)

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