結果
問題 | No.1856 Mex Sum 2 |
ユーザー |
|
提出日時 | 2021-04-17 17:48:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,350 ms / 3,000 ms |
コード長 | 1,789 bytes |
コンパイル時間 | 403 ms |
コンパイル使用メモリ | 81,844 KB |
実行使用メモリ | 77,632 KB |
最終ジャッジ日時 | 2024-07-04 04:43:53 |
合計ジャッジ時間 | 40,095 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 64 |
ソースコード
mod = 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], (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] = a[k] * w[s*t] % moda[j], a[k] = a[j]+a[k], a[j]-a[k]m <<= 1t //= 2n_inv = pow(n, mod-2, mod)for i in range(n):a[i] = a[i] * n_inv % modn, m = map(int, input().split())fixed_n = 1 << ((n+1)*2).bit_length()w_root = pow(3, (mod-1)//fixed_n, mod)w = [1] * fixed_nfor i in range(1, fixed_n):w[i] = w[i-1] * w_root % modfrac = [1] * (n + 1)for i in range(1, n+1):frac[i] = frac[i-1] * i % modfrac_inv = [0] * (n+1)frac_inv[n] = pow(frac[n], mod-2, mod)for i in range(1, n+1)[::-1]:frac_inv[i-1] = frac_inv[i] * i % moddp1 = [0] * fixed_ndp1[0] = 1t = [0] * fixed_nfor i in range(n+1):t[i] = (pow(2, i, mod)-1) * pow(pow(2, i, mod) * frac[i], mod-2, mod) % modfft_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 % modifft_inplace(dp1, w)pow_tmp = 1for i in range(k+1, n+1)[::-1]:ans_sub[i] += dp1[i] * pow_tmp % modpow_tmp = pow_tmp * (m - k) % modfor i in range(n+1, fixed_n):dp1[i] = 0ans = sum(ans_sub[i] % mod * frac_inv[n-i] for i in range(n+1)) % modans = ans * pow(2, n, mod) * frac[n] % modprint(ans)