結果

問題 No.3046 yukicoderの過去問
ユーザー Eki1009Eki1009
提出日時 2020-11-06 15:24:47
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 1,068 bytes
コンパイル時間 92 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 71,420 KB
最終ジャッジ日時 2024-07-22 11:47:42
合計ジャッジ時間 6,909 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 514 ms
44,676 KB
testcase_01 AC 520 ms
44,420 KB
testcase_02 AC 517 ms
44,164 KB
testcase_03 TLE -
testcase_04 AC 515 ms
44,796 KB
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
権限があれば一括ダウンロードができます

ソースコード

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