結果

問題 No.2062 Sum of Subset mod 999630629
ユーザー 👑 Nachia
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 M
template<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;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0