結果

問題 No.1025 Modular Equation
ユーザー gew1fw
提出日時 2025-06-12 13:27:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,061 bytes
コンパイル時間 529 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 76,048 KB
最終ジャッジ日時 2025-06-12 13:33:01
合計ジャッジ時間 9,708 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

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

    m = 0
    variables = []
    for ai in a:
        if ai == 0:
            m +=1
        else:
            variables.append(ai)
    
    dp = [0] * p
    dp[0] = 1

    for ai in variables:
        cnt = [0] * p
        for x in range(p):
            x_pow = pow(x, k, p)
            c = (ai * x_pow) % p
            cnt[c] += 1
        
        new_dp = [0] * p
        for s in range(p):
            if dp[s] == 0:
                continue
            for c in range(p):
                if cnt[c] == 0:
                    continue
                new_s = (s + c) % p
                new_dp[new_s] = (new_dp[new_s] + dp[s] * cnt[c]) % MOD
        
        dp = new_dp

    total = dp[b] * pow(p, m, MOD) % MOD
    print(total)

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