結果

問題 No.2396 等差二項展開
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:47:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,021 ms / 6,000 ms
コード長 1,304 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 75,996 KB
最終ジャッジ日時 2025-03-31 17:48:25
合計ジャッジ時間 20,804 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    N, M_val, L, K, B = map(int, sys.stdin.readline().split())
    mod = B
    M = M_val % mod
    
    def multiply(a, b, L, M, mod):
        res = [0] * L
        non_zero_a = [i for i in range(L) if a[i]]
        non_zero_b = [j for j in range(L) if b[j]]
        for i in non_zero_a:
            ai = a[i]
            for j in non_zero_b:
                bj = b[j]
                coeff = (ai * bj) % mod
                if coeff == 0:
                    continue
                k = i + j
                if k >= L:
                    coeff = (coeff * M) % mod
                    k -= L
                res[k] = (res[k] + coeff) % mod
        return res
    
    def pow_poly(n, L, M, mod):
        result = [0] * L
        result[0] = 1 % mod
        current_base = [0] * L
        current_base[0] = 1 % mod
        if L > 1:
            current_base[1] = 1 % mod
        else:
            current_base[0] = (1 + M) % mod
        
        while n > 0:
            if n % 2 == 1:
                result = multiply(result, current_base, L, M, mod)
            current_base = multiply(current_base, current_base, L, M, mod)
            n = n // 2
        return result
    
    poly = pow_poly(N, L, M, mod)
    print(poly[K] % mod)

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