結果
問題 | No.2062 Sum of Subset mod 999630629 |
ユーザー |
![]() |
提出日時 | 2022-08-27 02:34:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 806 ms / 5,000 ms |
コード長 | 6,058 bytes |
コンパイル時間 | 4,036 ms |
コンパイル使用メモリ | 261,472 KB |
最終ジャッジ日時 | 2025-01-31 06:05:58 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;typedef modint998244353 mint;typedef long long ll;// shobonfps// code from: https://opt-cp.com/fps-implementation/// but replaced "rep, drep" to "for"template<class T>struct FormalPowerSeries : vector<T> {using vector<T>::vector;using vector<T>::operator=;using F = FormalPowerSeries;F operator-() const {F res(*this);for (auto &e : res) e = -e;return res;}F &operator*=(const T &g) {for (auto &e : *this) e *= g;return *this;}F &operator/=(const T &g) {assert(g != T(0));*this *= g.inv();return *this;}F &operator+=(const F &g) {int n = (*this).size(), m = g.size();for(int i=0; i<min(n, m); i++) (*this)[i] += g[i];return *this;}F &operator-=(const F &g) {int n = (*this).size(), m = g.size();for(int i=0; i<min(n, m); i++) (*this)[i] -= g[i];return *this;}F &operator<<=(const int d) {int n = (*this).size();(*this).insert((*this).begin(), d, 0);(*this).resize(n);return *this;}F &operator>>=(const int d) {int n = (*this).size();(*this).erase((*this).begin(), (*this).begin() + min(n, d));(*this).resize(n);return *this;}F inv(int d = -1) const {int n = (*this).size();assert(n != 0 && (*this)[0] != 0);if (d == -1) d = n;assert(d > 0);F res{(*this)[0].inv()};while (res.size() < d) {int m = size(res);F f(begin(*this), begin(*this) + min(n, 2*m));F r(res);f.resize(2*m), internal::butterfly(f);r.resize(2*m), internal::butterfly(r);for(int i=0; i<2*m; i++) f[i] *= r[i];internal::butterfly_inv(f);f.erase(f.begin(), f.begin() + m);f.resize(2*m), internal::butterfly(f);for(int i=0; i<2*m; i++) f[i] *= r[i];internal::butterfly_inv(f);T iz = T(2*m).inv(); iz *= -iz;for(int i=0; i<m; i++) f[i] *= iz;res.insert(res.end(), f.begin(), f.begin() + m);}return {res.begin(), res.begin() + d};}// fast: FMT-friendly modulus onlyF &operator*=(const F &g) {int n = (*this).size();*this = convolution(*this, g);(*this).resize(n);return *this;}F &operator/=(const F &g) {int n = (*this).size();*this = convolution(*this, g.inv(n));(*this).resize(n);return *this;}// // naive// F &operator*=(const F &g) {// int n = (*this).size(), m = g.size();// for(int i=n-1; i>=0; i--) {// (*this)[i] *= g[0];// for(int j=1; j<min(i+1, m); j++) (*this)[i] += (*this)[i-j] * g[j];// }// return *this;// }// F &operator/=(const F &g) {// assert(g[0] != T(0));// T ig0 = g[0].inv();// int n = (*this).size(), m = g.size();// for(int i=0; i<n; i++) {// for(int j=1; j<min(i+1, m); j++) (*this)[i] -= (*this)[i-j] * g[j];// (*this)[i] *= ig0;// }// return *this;// }// sparseF &operator*=(vector<pair<int, T>> g) {int n = (*this).size();auto [d, c] = g.front();if (d == 0) g.erase(g.begin());else c = 0;for(int i=n-1; i>=0; i--) {(*this)[i] *= c;for (auto &[j, b] : g) {if (j > i) break;(*this)[i] += (*this)[i-j] * b;}}return *this;}F &operator/=(vector<pair<int, T>> g) {int n = (*this).size();auto [d, c] = g.front();assert(d == 0 && c != T(0));T ic = c.inv();g.erase(g.begin());for(int i=0; i<n; i++) {for (auto &[j, b] : g) {if (j > i) break;(*this)[i] -= (*this)[i-j] * b;}(*this)[i] *= ic;}return *this;}// multiply and divide (1 + cz^d)void multiply(const int d, const T c) {int n = (*this).size();if (c == T(1)) for(int i=n-d-1; i>=0; i--) (*this)[i+d] += (*this)[i];else if (c == T(-1)) for(int i=n-d-1; i>=0; i--) (*this)[i+d] -= (*this)[i];else for(int i=n-d-1; i>=0; i--) (*this)[i+d] += (*this)[i] * c;}void divide(const int d, const T c) {int n = (*this).size();if (c == T(1)) for(int i=0; i<n-d; i++) (*this)[i+d] -= (*this)[i];else if (c == T(-1)) for(int i=0; i<n-d; i++) (*this)[i+d] += (*this)[i];else for(int i=0; i<n-d; i++) (*this)[i+d] -= (*this)[i] * c;}T eval(const T &a) const {T x(1), res(0);for (auto e : *this) res += e * x, x *= a;return res;}F operator*(const T &g) const { return F(*this) *= g; }F operator/(const T &g) const { return F(*this) /= g; }F operator+(const F &g) const { return F(*this) += g; }F operator-(const F &g) const { return F(*this) -= g; }F operator<<(const int d) const { return F(*this) <<= d; }F operator>>(const int d) const { return F(*this) >>= d; }F operator*(const F &g) const { return F(*this) *= g; }F operator/(const F &g) const { return F(*this) /= g; }F operator*(vector<pair<int, T>> g) const { return F(*this) *= g; }F operator/(vector<pair<int, T>> g) const { return F(*this) /= g; }};typedef FormalPowerSeries<mint> fps;typedef vector<pair<int,mint>> sfps;//--------//defmodfactconst int COMinitMAX = 200000;mint fact[COMinitMAX+1], factinv[COMinitMAX+1];void modfact(){fact[0] = 1;for (int i=1; i<=COMinitMAX; i++){fact[i] = fact[i-1] * i;}factinv[COMinitMAX] = fact[COMinitMAX].inv();for (int i=COMinitMAX-1; i>=0; i--){factinv[i] = factinv[i+1] * (i+1);}}mint cmb(int a, int b){if (a<b || b<0) return mint(0);return fact[a]*factinv[b]*factinv[a-b];}//--------int main(){modfact();int N;cin >> N;vector<int> A(N);for (int i=0; i<N; i++){cin >> A[i];}mint ans = 0;mint nnv = mint(2).pow(N-1);vector<int> Q(10001);int asum = 0;for (int i=0; i<N; i++){cin >> A[i];ans += nnv * A[i];Q[A[i]] += 1;asum += A[i];}if (asum >= 999630629){int l = asum - 999630629 + 1;fps F(l);fps G(l);F[0] = 1;for (int i=1; i<min(l, 10001); i++){if (Q[i] > 1){for (int j=0; j<l; j+=i){G[j] = cmb(Q[i], j/i);}F *= G;for (int j=0; j<l; j+=i){G[j] = 0;}}else if(Q[i] == 1){F.multiply(i, 1);}}mint jogai = 0;for (int i=0; i<l; i++){jogai += F[i];}ans -= jogai * mint(999630629);}cout << ans.val() << endl;}