結果
問題 | No.2062 Sum of Subset mod 999630629 |
ユーザー | zkou |
提出日時 | 2022-08-26 23:04:39 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 9,012 bytes |
コンパイル時間 | 190 ms |
コンパイル使用メモリ | 82,272 KB |
実行使用メモリ | 164,116 KB |
最終ジャッジ日時 | 2024-10-13 23:42:19 |
合計ジャッジ時間 | 5,176 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
ソースコード
# For the sake of speed, # this convolution is specialized to mod 998244353. _fft_mod = 998244353 _fft_sum_e = ( 911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899, 0, 0, 0, 0, 0, 0, 0, 0, ) _fft_sum_ie = ( 86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235, 0, 0, 0, 0, 0, 0, 0, 0, ) def _butterfly(a): n = len(a) h = (n - 1).bit_length() for ph in range(1, h + 1): w = 1 << (ph - 1) p = 1 << (h - ph) now = 1 for s in range(w): offset = s << (h - ph + 1) for i in range(p): l = a[i + offset] r = a[i + offset + p] * now % _fft_mod a[i + offset] = (l + r) % _fft_mod a[i + offset + p] = (l - r) % _fft_mod now *= _fft_sum_e[(~s & -~s).bit_length() - 1] now %= _fft_mod def _butterfly_inv(a): n = len(a) h = (n - 1).bit_length() for ph in range(h, 0, -1): w = 1 << (ph - 1) p = 1 << (h - ph) inow = 1 for s in range(w): offset = s << (h - ph + 1) for i in range(p): l = a[i + offset] r = a[i + offset + p] a[i + offset] = (l + r) % _fft_mod a[i + offset + p] = (l - r) * inow % _fft_mod inow *= _fft_sum_ie[(~s & -~s).bit_length() - 1] inow %= _fft_mod def _convolution_naive(a, b): n = len(a) m = len(b) ans = [0] * (n + m - 1) if n < m: for j in range(m): for i in range(n): ans[i + j] = (ans[i + j] + a[i] * b[j]) % _fft_mod else: for i in range(n): for j in range(m): ans[i + j] = (ans[i + j] + a[i] * b[j]) % _fft_mod return ans def _convolution_fft(a, b): a = a.copy() b = b.copy() n = len(a) m = len(b) z = 1 << (n + m - 2).bit_length() a += [0] * (z - n) _butterfly(a) b += [0] * (z - m) _butterfly(b) for i in range(z): a[i] = a[i] * b[i] % _fft_mod _butterfly_inv(a) a = a[: n + m - 1] iz = pow(z, _fft_mod - 2, _fft_mod) for i in range(n + m - 1): a[i] = a[i] * iz % _fft_mod return a def _convolution_square(a): a = a.copy() n = len(a) z = 1 << (2 * n - 2).bit_length() a += [0] * (z - n) _butterfly(a) for i in range(z): a[i] = a[i] * a[i] % _fft_mod _butterfly_inv(a) a = a[: 2 * n - 1] iz = pow(z, _fft_mod - 2, _fft_mod) for i in range(2 * n - 1): a[i] = a[i] * iz % _fft_mod return a def convolution(a, b): """It calculates (+, x) convolution in mod 998244353. Given two arrays a[0], a[1], ..., a[n - 1] and b[0], b[1], ..., b[m - 1], it calculates the array c of length n + m - 1, defined by > c[i] = sum(a[j] * b[i - j] for j in range(i + 1)) % 998244353. It returns an empty list if at least one of a and b are empty. Complexity ---------- > O(n log n), where n = len(a) + len(b). """ n = len(a) m = len(b) if n == 0 or m == 0: return [] if min(n, m) <= 100: return _convolution_naive(a, b) if a is b: return _convolution_square(a) return _convolution_fft(a, b) # Reference: https://opt-cp.com/fps-fast-algorithms/ def inv(a): """It calculates the inverse of formal power series in O(n log n) time, where n = len(a).""" n = len(a) assert n > 0 and a[0] != 0 res = [pow(a[0], _fft_mod - 2, _fft_mod)] m = 1 while m < n: f = a[: min(n, 2 * m)] g = res.copy() f += [0] * (2 * m - len(f)) _butterfly(f) g += [0] * (2 * m - len(g)) _butterfly(g) for i in range(2 * m): f[i] = f[i] * g[i] % _fft_mod _butterfly_inv(f) f = f[m:] + [0] * m _butterfly(f) for i in range(2 * m): f[i] = f[i] * g[i] % _fft_mod _butterfly_inv(f) f = f[:m] iz = pow(2 * m, _fft_mod - 2, _fft_mod) iz *= -iz iz %= _fft_mod for i in range(m): f[i] = f[i] * iz % _fft_mod res.extend(f) m *= 2 res = res[:n] return res def integ_inplace(a): n = len(a) assert n > 0 if n == 1: return [] a.pop() a.insert(0, 0) inv = [1, 1] for i in range(2, n): inv.append(-inv[_fft_mod % i] * (_fft_mod // i) % _fft_mod) a[i] = a[i] * inv[i] % _fft_mod def deriv_inplace(a): n = len(a) assert n > 0 for i in range(2, n): a[i] = a[i] * i % _fft_mod a.pop(0) a.append(0) def log(a): a = a.copy() n = len(a) assert n > 0 and a[0] == 1 a_inv = inv(a) deriv_inplace(a) a = convolution(a, a_inv)[:n] integ_inplace(a) return a def exp(a): a = a.copy() n = len(a) assert n > 0 and a[0] == 0 g = [1] a[0] = 1 h_drv = a.copy() deriv_inplace(h_drv) m = 1 while m < n: f_fft = a[:m] + [0] * m _butterfly(f_fft) if m > 1: _f = [f_fft[i] * g_fft[i] % _fft_mod for i in range(m)] _butterfly_inv(_f) _f = _f[m // 2 :] + [0] * (m // 2) _butterfly(_f) for i in range(m): _f[i] = _f[i] * g_fft[i] % _fft_mod _butterfly_inv(_f) _f = _f[: m // 2] iz = pow(m, _fft_mod - 2, _fft_mod) iz *= -iz iz %= _fft_mod for i in range(m // 2): _f[i] = _f[i] * iz % _fft_mod g.extend(_f) t = a[:m] deriv_inplace(t) r = h_drv[: m - 1] r.append(0) _butterfly(r) for i in range(m): r[i] = r[i] * f_fft[i] % _fft_mod _butterfly_inv(r) im = pow(-m, _fft_mod - 2, _fft_mod) for i in range(m): r[i] = r[i] * im % _fft_mod for i in range(m): t[i] = (t[i] + r[i]) % _fft_mod t = [t[-1]] + t[:-1] t += [0] * m _butterfly(t) g_fft = g + [0] * (2 * m - len(g)) _butterfly(g_fft) for i in range(2 * m): t[i] = t[i] * g_fft[i] % _fft_mod _butterfly_inv(t) t = t[:m] i2m = pow(2 * m, _fft_mod - 2, _fft_mod) for i in range(m): t[i] = t[i] * i2m % _fft_mod v = a[m : min(n, 2 * m)] v += [0] * (m - len(v)) t = [0] * (m - 1) + t + [0] integ_inplace(t) for i in range(m): v[i] = (v[i] - t[m + i]) % _fft_mod v += [0] * m _butterfly(v) for i in range(2 * m): v[i] = v[i] * f_fft[i] % _fft_mod _butterfly_inv(v) v = v[:m] i2m = pow(2 * m, _fft_mod - 2, _fft_mod) for i in range(m): v[i] = v[i] * i2m % _fft_mod for i in range(min(n - m, m)): a[m + i] = v[i] m *= 2 return a def pow_fps(a, k): a = a.copy() n = len(a) l = 0 while l < len(a) and not a[l]: l += 1 if l * k >= n: return [0] * n ic = pow(a[l], _fft_mod - 2, _fft_mod) pc = pow(a[l], k, _fft_mod) a = log([a[i] * ic % _fft_mod for i in range(l, len(a))]) for i in range(len(a)): a[i] = a[i] * k % _fft_mod a = exp(a) for i in range(len(a)): a[i] = a[i] * pc % _fft_mod a = [0] * (l * k) + a[: n - l * k] return a MOD = 998244353 table_len = 10**6 + 10 fac = [1, 1] for i in range(2, table_len): fac.append(fac[-1] * i % MOD) finv = [0] * table_len finv[-1] = pow(fac[-1], MOD - 2, MOD) for i in range(table_len - 1, 0, -1): finv[i - 1] = finv[i] * i % MOD def comb(n, k): if k < 0 or n < 0 or n - k < 0: return 0 return fac[n] * finv[k] % MOD * finv[n - k] % MOD from collections import Counter P1 = 998244353 P2 = 999630629 N = 10**5 As = [10000] * N # N = int(input()) # As = list(map(int, input().split())) answer = pow(2, N - 1, P1) * sum(As) % P1 # #{ S | P2 <= \sum_{i \in S} A_i } # = #{ S' | sum(As) - P2 > \sum_{i \in S'} A_i } weight_ub = sum(As) - P2 if weight_ub <= 0: print(answer) exit() prod = [1] for A, count in Counter(As).items(): f = [0] * (weight_ub) for i in range((weight_ub - 1) // A + 1): f[i * A] = comb(count, i) prod = convolution(prod, f)[:weight_ub] answer -= P2 * (sum(prod) % P1) % P1 answer %= P1 print(answer)