結果
問題 | No.1857 Gacha Addiction |
ユーザー |
|
提出日時 | 2022-02-24 23:34:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 4,263 ms / 6,000 ms |
コード長 | 2,839 bytes |
コンパイル時間 | 171 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 268,368 KB |
最終ジャッジ日時 | 2024-07-02 14:19:13 |
合計ジャッジ時間 | 129,350 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
import collectionsmod = 998244353def fft_inplace(a, w):n = len(a)m = nt = 1while m >= 2:mh = m >> 1for i in range(0, n, m):for s in range(mh):j, k = i+s, i+mh+sa[j], a[k] = (a[j]+a[k]) % mod, (a[j]-a[k])*w[s*t] % modm = mht *= 2def ifft_inplace(a, w):n = len(a)m = 2t = -(n >> 1)while m <= n:mh = m >> 1for i in range(0, n, m):for s in range(mh):j, k = i+s, i+mh+sa[k] *= w[s*t]a[j], a[k] = (a[j]+a[k]) % mod, (a[j]-a[k]) % modm <<= 1t //= 2n_inv = pow(n, mod-2, mod)for i in range(n):a[i] = a[i] * n_inv % moddef normal_convolution(a, b):n = max(len(a) + len(b) - 1, 1)c = [0] * nfor i in range(len(a)):for j in range(len(b)):c[i+j] += a[i] * b[j]for i in range(n):c[i] %= modreturn cdef convolution(a, b):n2 = max(len(a) + len(b), 1)if len(a) * len(b) < 1 << 6:return normal_convolution(a, b)n = 1 << (n2-1).bit_length()a = a + [0] * (n-len(a))b = b + [0] * (n-len(b))w_root = pow(3, (mod-1)//n, mod)w = [1] * nfor i in range(1, n):w[i] = w[i-1] * w_root % modfft_inplace(a, w)fft_inplace(b, w)c = [i*j % mod for i, j in zip(a, b)]ifft_inplace(c, w)return c[:n2]class Poly:def __init__(Self, coeffs):Self.coeffs = coeffsdef __add__(Self, other):n = max(len(Self.coeffs), len(other.coeffs))result = [0] * nfor idx, i in enumerate(Self.coeffs):result[idx] += ifor idx, i in enumerate(other.coeffs):result[idx] += iresult[idx] %= modreturn Poly(result)def __mul__(Self, other):return Poly(convolution(Self.coeffs, other.coeffs))class Fraction:def __init__(Self, num, den):Self.num = numSelf.den = dendef __add__(Self, other):return Fraction(Self.num * other.den + Self.den * other.num, Self.den * other.den)n, s = map(int, input().split())assert 1 <= n <= 15 * 10 ** 4assert n <= s < 998244353s_inv = pow(s, mod-2, mod)pp = list(map(int, input().split()))assert all(1 <= i for i in pp)assert sum(pp) == sp = [i * s_inv % mod for i in pp]fractions = collections.deque(Fraction(Poly([0, i ** 2 % mod]), Poly([1, i])) for i in p)while len(fractions) > 1:fractions.append(fractions.popleft() + fractions.popleft())ans = 0factorial = 2for i in range(1, n + 1):ans += fractions[0].num.coeffs[i] * factorial % modfactorial = factorial * (i + 2) % modans %= modprint(ans)try:x = input()assert x == ""except EOFError:pass