結果
問題 | No.2062 Sum of Subset mod 999630629 |
ユーザー |
👑 ![]() |
提出日時 | 2022-08-26 21:44:22 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,905 ms / 5,000 ms |
コード長 | 5,493 bytes |
コンパイル時間 | 4,314 ms |
コンパイル使用メモリ | 131,996 KB |
最終ジャッジ日時 | 2025-01-31 04:36:00 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <set>#include <atcoder/modint>using namespace std;using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;#define rep(i,n) for(int i=0; i<(int)(n); i++)// a^i mod Mtemplate<u64 MOD>u64 powm(u64 a,u64 i) {if(i == 0) return 1;u64 r = powm<MOD>(a*a%MOD,i/2);if(i&1) r = r*a%MOD;return r;}template<u64 MOD, u64 g>void NTT(vector<u64>& A){int N=1;while(N < A.size()) N *= 2;for(int i=0,j=0; j<N; j++){if(i<j) swap(A[i],A[j]);for(int k=N>>1; k>(i^=k); k>>=1);}for(int i=1; i<N; i<<=1){u64 q=powm<MOD>(g,(MOD-1)/i/2), qj=1;for(int j=0; j<i; j++){for(int k=j; k<N; k+=i*2){u64 l = A[k];u64 r = A[k+i] * qj % MOD;A[k] = l+r;if(A[k] >= MOD) A[k] -= MOD;A[k+i] = l+MOD-r;if(A[k+i] >= MOD) A[k+i] -= MOD;}qj = qj * q % MOD;}}}template<u64 MOD, u64 g>vector<u64> convolution(const vector<u64>& A, const vector<u64>& B){int Z = 1; while(Z < A.size() + B.size()) Z *= 2;vector<u64> Ax(Z), Bx(Z);u64 iZ = powm<MOD>(Z, MOD-2);rep(i, A.size()) Ax[i] = A[i];rep(i, B.size()) Bx[i] = B[i];NTT<MOD,g>(Ax); NTT<MOD,g>(Bx);rep(i,Z) Ax[i] = Ax[i] * Bx[i] % MOD;NTT<MOD,g>(Ax);reverse(Ax.begin() + 1, Ax.end());rep(i,Z) Ax[i] = Ax[i] * iZ % MOD;Ax.resize(A.size() + B.size() - 1);return move(Ax);}template<u64 MOD, u64 g>vector<u64> powsumFPS(const vector<u64>& A, int n){if(n == 0){ return {}; }if(n == 1){ return { 1 }; }int N = 1; while(N<n) N*=2;int hN = N/2;vector<u64> hInv = powsumFPS<MOD,g>(A,hN);vector<u64> tgA(N,0);for(int i=0; i<min(N,(int)A.size()); i++) tgA[i] = A[i];u64 ig = powm<MOD>(g,MOD-2);NTT<MOD,g>(tgA);vector<u64> htInv(N,0);for(int i=0; i<hN; i++) htInv[i] = hInv[i];NTT<MOD,g>(htInv);vector<u64> R(N);for(int i=0; i<N; i++) R[i] = tgA[i] * htInv[i] % MOD;NTT<MOD,g>(R); reverse(R.begin()+1, R.end());for(int i=0; i<hN; i++) R[i] = R[hN+i];for(int i=hN; i<N; i++) R[i] = 0;NTT<MOD,g>(R);u64 iNN = powm<MOD>((u64)N*N%MOD,MOD-2);for(int i=0; i<N; i++) R[i] = R[i] * htInv[i] % MOD * iNN % MOD;NTT<MOD,g>(R); reverse(R.begin()+1, R.end());hInv.resize(n,0);for(int i=hN; i<n; i++) hInv[i] = R[i-hN];return move(hInv);}template<u64 MOD, u64 g>vector<u64> invFPS(const vector<u64>& A, int n){u64 iA0 = powm<MOD>(A[0],MOD-2);vector<u64> xA(min(n,(int)A.size()));for(int i=0; i<xA.size(); i++) xA[i] = (MOD - A[i]) * iA0 % MOD;xA[0] = 0;xA = powsumFPS<MOD,g>(xA,n);for(int i=0; i<xA.size(); i++) xA[i] = xA[i] * iA0 % MOD;return move(xA);}static vector<u64> InvMOD = {1,1};template<u64 MOD, u64 g>vector<u64> logFPS(const vector<u64>& A, int n){int z = A.size();for(int i=InvMOD.size(); i<=n; i++){InvMOD.push_back((MOD - MOD/i) * InvMOD[MOD%i] % MOD);}auto res = invFPS<MOD,g>(A, n);vector<u64> Abuf(z);rep(i,z-1) Abuf[i] = A[i+1] * (i+1) % MOD;res = convolution<MOD,g>(res, Abuf);res.resize(n);for(int i=n-2; i>=0; i--) res[i+1] = res[i] * InvMOD[i+1] % MOD;res[0] = 0;return res;}template<u64 MOD, u64 g>vector<u64> expFPS(const vector<u64>& A, int n){vector<u64> res = {1};while(res.size() < n){int z = res.size();auto tmp = logFPS<MOD,g>(res,z*2);tmp[0] = MOD - 1;rep(i,min<int>(z*2,A.size())){tmp[i] = MOD - tmp[i] + A[i];if(tmp[i] >= MOD) tmp[i] -= MOD;}res = convolution<MOD,g>(res, tmp);res.resize(min(n,2*z));}return res;}template<u64 MOD, u64 g>vector<u64> powFPS(const vector<u64>& A, u64 k){int n = A.size();int zerocnt = 0;rep(i,n) if(A[i] == 0) zerocnt = i+1; else break;if(zerocnt >= (n-1)/k+1) return vector<u64>(n,0);auto res = A;rep(i,n-zerocnt) res[i] = res[i+zerocnt];i64 A0 = res[0];i64 iA0 = powm<MOD>(A0,MOD-2);i64 pA0 = powm<MOD>(A0,k);rep(i,n) res[i] = res[i] * iA0 % MOD;res = logFPS<MOD,g>(res,n);rep(i,n) res[i] = res[i] * k % MOD;res = expFPS<MOD,g>(res,n);rep(i,n) res[i] = res[i] * pA0 % MOD;zerocnt *= k;res.resize(n);for(int i=n-1; i>=zerocnt; i--) res[i] = res[i-zerocnt];rep(i, zerocnt) res[i] = 0;return res;}template<u64 MOD, u64 g>vector<u64> SubsetSum(const vector<u64>& D){int n = D.size();for(int i=InvMOD.size(); i<=n; i++){InvMOD.push_back((MOD - MOD/i) * InvMOD[MOD%i] % MOD);}vector<u64> A(n);for(int i=1; i<n; i++) if(D[i] != 0){u64 tmp = i * D[i] % MOD;for(int a=i; a<n; a+=i){A[a] = (A[a] + tmp * InvMOD[a]) % MOD;tmp = MOD - tmp;}}rep(i,n+1) A[i] %= MOD;A = expFPS<MOD,g>(A, n);return A;}const i64 INF = 1001001001001001001;using modint = atcoder::static_modint<998244353>;int main(){int N; cin >> N;vector<int> A(N);rep(i,N) cin >> A[i];int G = 999630629;int sumA = 0; for(int a : A) sumA += a;modint ans = sumA;ans *= modint(2).pow(N-1);if(sumA >= G){vector<u64> Q(sumA-G+1);for(int a : A) Q[a] += 1;Q = SubsetSum<998244353,3>(Q);modint q = 0;for(auto qq : Q) q += qq;ans -= q * modint(G);}cout << ans.val() << '\n';return 0;}struct ios_do_not_sync{ios_do_not_sync(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}} ios_do_not_sync_instance;