結果
| 問題 | No.2062 Sum of Subset mod 999630629 |
| ユーザー |
 zkou
|
| 提出日時 | 2022-08-26 23:14:03 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,969 bytes |
| コンパイル時間 | 194 ms |
| コンパイル使用メモリ | 82,176 KB |
| 実行使用メモリ | 416,732 KB |
| 最終ジャッジ日時 | 2024-10-13 23:54:16 |
| 合計ジャッジ時間 | 28,488 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 WA * 18 TLE * 1 |
ソースコード
# For the sake of speed,# this convolution is specialized to mod 998244353._fft_mod = 998244353_fft_imag = 911660635_fft_iimag = 86583718_fft_rate2 = (911660635,509520358,369330050,332049552,983190778,123842337,238493703,975955924,603855026,856644456,131300601,842657263,730768835,942482514,806263778,151565301,510815449,503497456,743006876,741047443,56250497,867605899,)_fft_irate2 = (86583718,372528824,373294451,645684063,112220581,692852209,155456985,797128860,90816748,860285882,927414960,354738543,109331171,293255632,535113200,308540755,121186627,608385704,438932459,359477183,824071951,103369235,)_fft_rate3 = (372528824,337190230,454590761,816400692,578227951,180142363,83780245,6597683,70046822,623238099,183021267,402682409,631680428,344509872,689220186,365017329,774342554,729444058,102986190,128751033,395565204,)_fft_irate3 = (509520358,929031873,170256584,839780419,282974284,395914482,444904435,72135471,638914820,66769500,771127074,985925487,262319669,262341272,625870173,768022760,859816005,914661783,430819711,272774365,530924681,)def _butterfly(a):n = len(a)h = (n - 1).bit_length()len_ = 0while len_ < h:if h - len_ == 1:p = 1 << (h - len_ - 1)rot = 1for s in range(1 << len_):offset = s << (h - len_)for i in range(p):l = a[i + offset]r = a[i + offset + p] * rota[i + offset] = (l + r) % _fft_moda[i + offset + p] = (l - r) % _fft_modif s + 1 != (1 << len_):rot *= _fft_rate2[(~s & -~s).bit_length() - 1]rot %= _fft_modlen_ += 1else:p = 1 << (h - len_ - 2)rot = 1for s in range(1 << len_):rot2 = rot * rot % _fft_modrot3 = rot2 * rot % _fft_modoffset = s << (h - len_)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p] * rota2 = a[i + offset + p * 2] * rot2a3 = a[i + offset + p * 3] * rot3a1na3imag = (a1 - a3) % _fft_mod * _fft_imaga[i + offset] = (a0 + a2 + a1 + a3) % _fft_moda[i + offset + p] = (a0 + a2 - a1 - a3) % _fft_moda[i + offset + p * 2] = (a0 - a2 + a1na3imag) % _fft_moda[i + offset + p * 3] = (a0 - a2 - a1na3imag) % _fft_modif s + 1 != (1 << len_):rot *= _fft_rate3[(~s & -~s).bit_length() - 1]rot %= _fft_modlen_ += 2def _butterfly_inv(a):n = len(a)h = (n - 1).bit_length()len_ = hwhile len_:if len_ == 1:p = 1 << (h - len_)irot = 1for s in range(1 << (len_ - 1)):offset = s << (h - len_ + 1)for i in range(p):l = a[i + offset]r = a[i + offset + p]a[i + offset] = (l + r) % _fft_moda[i + offset + p] = (l - r) * irot % _fft_modif s + 1 != (1 << (len_ - 1)):irot *= _fft_irate2[(~s & -~s).bit_length() - 1]irot %= _fft_modlen_ -= 1else:p = 1 << (h - len_)irot = 1for s in range(1 << (len_ - 2)):irot2 = irot * irot % _fft_modirot3 = irot2 * irot % _fft_modoffset = s << (h - len_ + 2)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p]a2 = a[i + offset + p * 2]a3 = a[i + offset + p * 3]a2na3iimag = (a2 - a3) * _fft_iimag % _fft_moda[i + offset] = (a0 + a1 + a2 + a3) % _fft_moda[i + offset + p] = ((a0 - a1 + a2na3iimag) * irot % _fft_mod)a[i + offset + p * 2] = ((a0 + a1 - a2 - a3) * irot2 % _fft_mod)a[i + offset + p * 3] = ((a0 - a1 - a2na3iimag) * irot3 % _fft_mod)if s + 1 != (1 << (len_ - 2)):irot *= _fft_irate3[(~s & -~s).bit_length() - 1]irot %= _fft_modlen_ -= 2def _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] += a[i] * b[j]ans[i + j] %= _fft_modelse:for i in range(n):for j in range(m):ans[i + j] += a[i] * b[j]ans[i + j] %= _fft_modreturn ansdef _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] *= b[i]a[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] *= iza[i] %= _fft_modreturn adef _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] *= iza[i] %= _fft_modreturn adef 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.Constraints-----------> len(a) + len(b) <= 8388609Complexity----------> 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) <= 60:return _convolution_naive(a, b)if a is b:return _convolution_square(a)return _convolution_fft(a, b)MOD = 998244353table_len = 10**6 + 10fac = [1, 1]for i in range(2, table_len):fac.append(fac[-1] * i % MOD)finv = [0] * table_lenfinv[-1] = pow(fac[-1], MOD - 2, MOD)for i in range(table_len - 1, 0, -1):finv[i - 1] = finv[i] * i % MODdef comb(n, k):if k < 0 or n < 0 or n - k < 0:return 0return fac[n] * finv[k] % MOD * finv[n - k] % MODfrom collections import CounterP1 = 998244353P2 = 999630629# N = 10**5# As = [10000] * NN = 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) - P2if 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 // A):f[i * A] = comb(count, i)prod = convolution(prod, f)[:weight_ub]answer -= P2 * (sum(prod) % P1) % P1answer %= P1print(answer)