結果
問題 | No.1073 無限すごろく |
ユーザー |
![]() |
提出日時 | 2020-06-05 22:37:09 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 507 ms / 2,000 ms |
コード長 | 1,366 bytes |
コンパイル時間 | 89 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 44,148 KB |
最終ジャッジ日時 | 2024-12-17 16:35:01 |
合計ジャッジ時間 | 17,941 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import sysimport numpy as npread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesMOD = 10**9 + 7def convolve(f, g, MOD=MOD):Lf = len(f)Lg = len(g)fl = f & (1 << 15) - 1fh = f >> 15gl = g & (1 << 15) - 1gh = g >> 15def conv(f, g):return np.convolve(f, g) % MODx = conv(fl, gl)y = conv(fl + fh, gl + gh)z = conv(fh, gh)a, b, c = map(lambda x: (x + .5).astype(np.int64), [x, y, z])return (a + ((b - a - c) << 15) + (c << 30)) % MODdef coef_of_generating_function(P, Q, N):"""compute the coefficient [x^N] P/Q of rational power series.Parameters----------P : np.ndarraynumerator.Q : np.ndarraydenominatorQ[0] == 1 and len(Q) == len(P) + 1 is assumed.N : intThe coefficient to compute."""def conv(f, g):return convolve(f, g, MOD)while N:Q1 = Q.copy()Q1[1::2] = np.negative(Q1[1::2])if N & 1:P = conv(P, Q1)[1::2]else:P = conv(P, Q1)[::2]Q = conv(Q, Q1)[::2]N >>= 1return P[0]N = int(read())t = -pow(6, MOD - 2, MOD)num = np.array([1, 0, 0, 0, 0, 0], np.int64)den = np.array([1, t, t, t, t, t, t], np.int64)print(coef_of_generating_function(num, den, N))