結果

問題 No.8046 yukicoderの過去問
コンテスト
ユーザー Eki1009
提出日時 2020-11-06 15:24:47
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,068 bytes
コンパイル時間 92 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 71,420 KB
最終ジャッジ日時 2024-07-22 11:47:42
合計ジャッジ時間 6,909 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import numpy as np
mod = 1000000007
def convolution(a, b):
    n = len(a)
    m = len(b)
    l = n + m - 1
    z = 1 << (l - 1).bit_length()
    ah, al = a >> 15, a & ((1 << 15) - 1)
    bh, bl = b >> 15, b & ((1 << 15) - 1)
    p = np.rint(np.fft.irfft(np.fft.rfft(al, z) * np.fft.rfft(bl, z))[:l]).astype(np.int64)
    r = np.rint(np.fft.irfft(np.fft.rfft(ah, z) * np.fft.rfft(bh, z))[:l]).astype(np.int64)
    q = np.rint(np.fft.irfft(np.fft.rfft(al + ah, z) * np.fft.rfft(bl + bh, z))[:l]).astype(np.int64) - p - r
    return ((p + (q << 15)) + (r << 30)) % mod

#[x^n]P/Qを求める
def poly_coef(Q, P, n):
    while n:
        R = np.empty_like(Q)
        R[::2] = Q[::2]
        R[1::2] = -Q[1::2]
        P = convolution(P, R)
        Q = convolution(Q, R)
        P = P[n & 1::2]
        Q = Q[::2]
        n >>= 1
    return P[0]


import sys
input = sys.stdin.readline
k = int(input())
n = int(input())
X  = np.array(list(map(int, input().split())))
Q = np.zeros(k+1, dtype=np.int64)
Q[0] = 1
Q[X] = -1
P = np.array([1])
ans = poly_coef(Q, P, k)
print(ans)
0