結果
問題 | No.1857 Gacha Addiction |
ユーザー |
|
提出日時 | 2021-12-31 22:51:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 4,371 ms / 6,000 ms |
コード長 | 2,354 bytes |
コンパイル時間 | 166 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 292,392 KB |
最終ジャッジ日時 | 2024-07-01 21:59:28 |
合計ジャッジ時間 | 133,295 ms |
ジャッジサーバーID (参考情報) |
judge3 / 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 <<= 1def 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 zero_pad(a, n):a.extend([0] * (n - len(a)))def zero_remove(a, n):for _ in range(len(a) - n):a.pop()class Fraction:def __init__(self, num, den):self.num = numself.den = dendef __add__(self, other):a_num = self.numa_den = self.denb_num = other.numb_den = other.denn2 = max(len(a_num) + len(b_num) - 1, 1)n = 1 << (n2-1).bit_length()zero_pad(a_num, n)zero_pad(a_den, n)zero_pad(b_num, n)zero_pad(b_den, n)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_num, w)fft_inplace(a_den, w)fft_inplace(b_num, w)fft_inplace(b_den, w)c_num = [(a * d + b * c) % mod for a, b, c, d in zip(a_num, a_den, b_num, b_den)]c_dem = [a * b % mod for a, b in zip(a_den, b_den)]ifft_inplace(c_num, w)ifft_inplace(c_dem, w)zero_remove(c_num, n)zero_remove(c_dem, n)return Fraction(c_num, c_dem)n, s = map(int, input().split())s_inv = pow(s, mod-2, mod)p = [i * s_inv % mod for i in map(int, input().split())]fractions = collections.deque(Fraction([0, i ** 2 % mod], [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[i] * factorial % modfactorial = factorial * (i + 2) % modans %= modprint(ans)