結果
問題 | No.1856 Mex Sum 2 |
ユーザー |
|
提出日時 | 2021-04-17 17:53:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,326 ms / 3,000 ms |
コード長 | 1,928 bytes |
コンパイル時間 | 232 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 77,316 KB |
最終ジャッジ日時 | 2024-07-04 04:46:43 |
合計ジャッジ時間 | 38,239 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 64 |
ソースコード
def 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], u = a[j]+a[k], a[j]-a[k]a[k] = u * w[s*t] % 998244353m = 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+su = a[k] * w[s*t] % 998244353a[j], a[k] = a[j]+u, a[j]-um <<= 1t //= 2n_inv = pow(n, 998244353-2, 998244353)for i in range(n):a[i] = a[i] * n_inv % 998244353n, m = map(int, input().split())fixed_n = 1 << ((n+1)*2).bit_length()w_root = pow(3, (998244353-1)//fixed_n, 998244353)w = [1] * fixed_nfor i in range(1, fixed_n):w[i] = w[i-1] * w_root % 998244353frac = [1] * (n + 1)for i in range(1, n+1):frac[i] = frac[i-1] * i % 998244353frac_inv = [0] * (n+1)frac_inv[n] = pow(frac[n], 998244353-2, 998244353)for i in range(1, n+1)[::-1]:frac_inv[i-1] = frac_inv[i] * i % 998244353dp1 = [0] * fixed_ndp1[0] = 1t = [0] * fixed_nfor i in range(n+1):t[i] = (pow(2, i, 998244353)-1) * pow(pow(2, i, 998244353) * frac[i], 998244353-2, 998244353) % 998244353fft_inplace(t, w)ans_sub = [0] * (n+1)for k in range(min(n, m+1)):fft_inplace(dp1, w)for i, j in enumerate(t):dp1[i] = dp1[i] * j % 998244353ifft_inplace(dp1, w)pow_tmp = 1for i in range(k+1, n+1)[::-1]:ans_sub[i] += dp1[i] * pow_tmp % 998244353pow_tmp = pow_tmp * (m - k) % 998244353for i in range(n+1, fixed_n):dp1[i] = 0ans = sum(ans_sub[i] % 998244353 * frac_inv[n-i] for i in range(n+1)) % 998244353ans = ans * pow(2, n, 998244353) * frac[n] % 998244353print(ans)