結果

問題 No.1025 Modular Equation
ユーザー gew1fw
提出日時 2025-06-12 13:41:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,400 bytes
コンパイル時間 323 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 76,100 KB
最終ジャッジ日時 2025-06-12 13:45:31
合計ジャッジ時間 10,375 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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]))
    
    if p == 1:
        print(1 if b == 0 else 0)
        return
    
    r = k % (p-1) if p != 2 else 0
    
    dp = [0] * p
    dp[0] = 1
    
    for ai in a:
        if ai == 0:
            for j in range(p):
                dp[j] = (dp[j] * p) % MOD
            continue
        
        cnt = {}
        if r == 0:
            cnt[0] = 1
            ai_mod = ai % p
            if ai_mod in cnt:
                cnt[ai_mod] += (p-1)
            else:
                cnt[ai_mod] = p-1
        else:
            cnt = {}
            for xi in range(p):
                if xi == 0:
                    vi = 0
                else:
                    xi_mod = pow(xi, r, p)
                    vi = (ai * xi_mod) % p
                if vi in cnt:
                    cnt[vi] += 1
                else:
                    cnt[vi] = 1
        
        new_dp = [0] * p
        for j in range(p):
            for v in cnt:
                prev = (j - v) % p
                new_dp[j] = (new_dp[j] + dp[prev] * cnt[v]) % MOD
        dp = new_dp
    
    print(dp[b] % MOD)

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