結果

問題 No.1025 Modular Equation
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:31:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,301 bytes
コンパイル時間 401 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 76,780 KB
最終ジャッジ日時 2025-06-12 13:36:38
合計ジャッジ時間 9,714 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 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(map(int, input[ptr:ptr+n]))
    ptr +=n

    if p == 1:
        print(0)
        return

    # Precompute k' = k mod (p-1) if xi !=0
    if p ==1:
        k_prime =0
    else:
        k_prime = k % (p-1)

    # Precompute for each i, the count of c_i
    cnt = []
    for ai in a:
        c_cnt = [0]*p
        for xi in range(p):
            if xi ==0:
                xk = 0
            else:
                xk = pow(xi, k_prime, p)
            c = (ai * xk) % p
            c_cnt[c] +=1
        cnt.append(c_cnt)

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

    # For each i, multiply dp with cnt_i
    for i in range(n):
        c_cnt = cnt[i]
        # Create new_dp
        new_dp = [0]*p
        for s in range(p):
            if dp[s] ==0:
                continue
            for c in range(p):
                if c_cnt[c] ==0:
                    continue
                new_s = (s + c) % p
                new_dp[new_s] = (new_dp[new_s] + dp[s] * c_cnt[c]) % MOD
        dp = new_dp

    print(dp[b] % MOD)

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