結果

問題 No.1025 Modular Equation
ユーザー gew1fw
提出日時 2025-06-12 19:04:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,865 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,068 KB
実行使用メモリ 440,348 KB
最終ジャッジ日時 2025-06-12 19:04:36
合計ジャッジ時間 9,196 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().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
    
    # Precompute f(c) for all c in 0..p-1
    f = [0] * p
    if p == 1:
        # Edge case, but p >=2 in input
        pass
    else:
        g = 1
        if p != 1:
            g = pow(k, p-2, p-1)
            g = pow(k, g, p)
        # Wait, no. Let's compute g = gcd(k, p-1)
        g_val = gcd(k, p-1)
        # Compute f(c)
        f[0] = 1
        if p-1 ==0:
            # p=1, but input p >=2
            pass
        else:
            e = (p-1) // g_val
            for c in range(1, p):
                res = pow(c, e, p)
                if res ==1:
                    f[c] = g_val
                else:
                    f[c] =0
    
    # Precompute cnt_i for each a_i
    cnt_list = []
    zero_count =0
    for ai in a:
        if ai ==0:
            zero_count +=1
            continue
        inv_ai = pow(ai, p-2, p)
        cnt = [0]*p
        for v in range(p):
            c = (v * inv_ai) % p
            cnt[v] = f[c]
        cnt_list.append(cnt)
    
    # Compute DP
    dp = [0]*p
    dp[0] =1
    for cnt in cnt_list:
        new_dp = [0]*p
        for s in range(p):
            if dp[s] ==0:
                continue
            for v in range(p):
                if cnt[v] ==0:
                    continue
                new_s = (s + v) % p
                new_dp[new_s] = (new_dp[new_s] + dp[s] * cnt[v]) % MOD
        dp = new_dp
    
    # Multiply by p^zero_count mod MOD
    ans = dp[b] * pow(p, zero_count, MOD) % MOD
    print(ans)
    
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

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