結果
問題 | No.1857 Gacha Addiction |
ユーザー |
|
提出日時 | 2021-12-31 22:57:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 5,456 ms / 6,000 ms |
コード長 | 3,102 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 282,836 KB |
最終ジャッジ日時 | 2024-07-01 21:53:05 |
合計ジャッジ時間 | 127,020 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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()def normal_convolution(a, b):n = max(len(a) + len(b) - 1, 1)c = [0] * nfor idx1, i in enumerate(a):for idx2, j in enumerate(b):c[idx1 + idx2] += i * jreturn cdef normal_convolution_mod(a, b):n = max(len(a) + len(b) - 1, 1)c = [0] * nfor idx1, i in enumerate(a):for idx2, j in enumerate(b):c[idx1 + idx2] += i * jfor i in range(n):c[i] %= modreturn cclass 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)if n2 < 128:c_num = [(i + j ) % mod for i,j in zip(normal_convolution(a_num, b_den), normal_convolution(b_num, a_den))]c_den = normal_convolution_mod(a_den, b_den)else: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_den = [a * b % mod for a, b in zip(a_den, b_den)]ifft_inplace(c_num, w)ifft_inplace(c_den, w)zero_remove(c_num, n)zero_remove(c_den, n)return Fraction(c_num, c_den)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)