結果

問題 No.2396 等差二項展開
ユーザー lam6er
提出日時 2025-03-20 20:43:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,290 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 76,516 KB
最終ジャッジ日時 2025-03-20 20:44:37
合計ジャッジ時間 33,233 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 29 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def multiply(a, b, L, M, B):
    res = [0] * L
    for i in range(L):
        if a[i] == 0:
            continue
        for j in range(L):
            if b[j] == 0:
                continue
            t = a[i] * b[j] % B
            exp = i + j
            if exp >= L:
                t = t * (M % B) % B
                exp -= L
            res[exp % L] = (res[exp % L] + t) % B
    return res

def poly_pow(poly, N, L, M, B):
    result = [0] * L
    result[0] = 1 % B  # Initialize as 1 polynomial
    current = poly[:]
    while N > 0:
        if N % 2 == 1:
            result = multiply(result, current, L, M, B)
        current = multiply(current, current, L, M, B)
        N = N // 2
    return result

def main():
    import sys
    input_line = sys.stdin.readline().strip()
    N, M_val, L, K, B = map(int, input_line.split())
    
    # The polynomial starts as (1 + x), which is represented with coefficients [1, 1, 0, ..., 0] of length L.
    poly = [0] * L
    poly[0] = 1 % B
    if 1 < L:
        poly[1] = 1 % B
    else:
        # In case L=1, x^1 is the same as x^0 * M_val because x^1 ≡ M_val (mod x^L - M)
        poly[0] = (poly[0] + 1) % B
    
    result_poly = poly_pow(poly, N, L, M_val, B)
    print(result_poly[K] % B)

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