結果
問題 | No.2633 Subsequence Combination Score |
ユーザー |
|
提出日時 | 2024-02-16 22:28:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 374 ms / 2,000 ms |
コード長 | 6,410 bytes |
コンパイル時間 | 2,390 ms |
コンパイル使用メモリ | 187,856 KB |
実行使用メモリ | 48,656 KB |
最終ジャッジ日時 | 2024-09-28 21:02:11 |
合計ジャッジ時間 | 18,475 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define app push_back#define all(x) (x).begin(),(x).end()#ifdef LOCAL#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)#else#define debug(...)#endif#ifdef LOCAL#define __int128 long long#endif // LOCALtypedef long long ll;const int p=998244353;int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}int inv(int x) {return po(x,p-2);}template<int M, int K, int G> struct Fft {// 1, 1/4, 1/8, 3/8, 1/16, 5/16, 3/16, 7/16, ...int g[1 << (K - 1)];Fft() : g() { //if tl constexpr...static_assert(K >= 2, "Fft: K >= 2 must hold");g[0] = 1;g[1 << (K - 2)] = G;for (int l = 1 << (K - 2); l >= 2; l >>= 1) {g[l >> 1] = (static_cast<long long>(g[l]) * g[l]) % M;}assert((static_cast<long long>(g[1]) * g[1]) % M == M - 1);for (int l = 2; l <= 1 << (K - 2); l <<= 1) {for (int i = 1; i < l; ++i) {g[l + i] = (static_cast<long long>(g[l]) * g[i]) % M;}}}void fft(vector<int> &x) const {const int n = x.size();assert(!(n & (n - 1)) && n <= 1 << K);for (int h = __builtin_ctz(n); h--; ) {const int l = 1 << h;for (int i = 0; i < n >> 1 >> h; ++i) {for (int j = i << 1 << h; j < ((i << 1) + 1) << h; ++j) {const int t = (static_cast<long long>(g[i]) * x[j | l]) % M;if ((x[j | l] = x[j] - t) < 0) x[j | l] += M;if ((x[j] += t) >= M) x[j] -= M;}}}for (int i = 0, j = 0; i < n; ++i) {if (i < j) std::swap(x[i], x[j]);for (int l = n; (l >>= 1) && !((j ^= l) & l); ) {}}}vector<int> convolution(const vector<int> &a, const vector<int> &b) const {if(a.empty() || b.empty()) return {};const int na = a.size(), nb = b.size();int n, invN = 1;for (n = 1; n < na + nb - 1; n <<= 1) invN = ((invN & 1) ? (invN + M) : invN) >> 1;vector<int> x(n, 0), y(n, 0);std::copy(a.begin(), a.end(), x.begin());std::copy(b.begin(), b.end(), y.begin());fft(x);fft(y);for (int i = 0; i < n; ++i) x[i] = (((static_cast<long long>(x[i]) * y[i]) % M) * invN) % M;std::reverse(x.begin() + 1, x.end());fft(x);x.resize(na + nb - 1);return x;}};Fft<998244353,23,31> muls;vector<int> form(vector<int> v,int n){while(v.size()<n) v.push_back(0);while(v.size()>n) v.pop_back();return v;}vector<int> operator *(vector<int> v1,vector<int> v2){return muls.convolution(v1,v2);}vector<int> operator +(vector<int> v1,vector<int> v2){while(v2.size()<v1.size()) v2.push_back(0); while(v1.size()<v2.size()) v1.push_back(0);for(int i=0;i<v1.size();++i) {v1[i]+=v2[i];if(v1[i]>=p) v1[i]-=p; else if(v1[i]<0) v1[i]+=p;}return v1;}vector<int> operator -(vector<int> v1,vector<int> v2){int sz=max(v1.size(),v2.size());while(v1.size()<sz) v1.push_back(0); while(v2.size()<sz) v2.push_back(0);for(int i=0;i<sz;++i) {v1[i]-=v2[i];if(v1[i]<0) v1[i]+=p; else if(v1[i]>=p) v1[i]-=p;} return v1;}vector<int> trmi(vector<int> v){for(int i=1;i<v.size();i+=2) {if(v[i]>0) v[i]=p-v[i]; else v[i]=(-v[i]);}return v;}vector<int> deriv(vector<int> v){if(v.empty()) return{};vector<int> ans(v.size()-1);for(int i=1;i<v.size();++i) ans[i-1]=(v[i]*1LL*i)%p;return ans;}vector<int> integ(vector<int> v){vector<int> ans(v.size()+1);ans[0]=0;for(int i=1;i<v.size();++i) ans[i-1]=(v[i]*1LL*i)%p;return ans;}vector<int> mul(vector<vector<int> > v){if(v.size()==1) return v[0];vector<vector<int> > v1,v2;for(int i=0;i<v.size()/2;++i) v1.push_back(v[i]); for(int i=v.size()/2;i<v.size();++i) v2.push_back(v[i]);return muls.convolution(mul(v1),mul(v2));}vector<int> inv1(vector<int> v,int n){assert(v[0]!=0);int sz=1;v=form(v,n);vector<int> a={inv(v[0])};while(sz<n){vector<int> vsz;for(int i=0;i<min(n,2*sz);++i) vsz.push_back(v[i]);vector<int> b=((vector<int>) {1})-muls.convolution(a,vsz);for(int i=0;i<sz;++i) assert(b[i]==0);b.erase(b.begin(),b.begin()+sz);vector<int> c=muls.convolution(b,a);for(int i=0;i<sz;++i) a.push_back(c[i]);sz*=2;}return form(a,n);}vector<int> inv(vector<int> v,int n){v=form(v,n);assert(v[0]!=0);if(v.size()==1) {return {inv(v[0])};} vector<int> v1=trmi(v);vector<int> a=v1*v;a=form(a,2*n);vector<int> b((n+1)/2);for(int i=0;i<b.size();++i) b[i]=a[2*i];vector<int> ans1=inv(b,b.size());vector<int> ans2(n);for(int i=0;i<n;++i) {if(i%2==0) ans2[i]=ans1[i/2]; else ans2[i]=0;}return form(v1*ans2,n);}vector<int> operator/(vector<int> a,vector<int> b){while(!a.empty() && a.back()==0) a.pop_back(); while(!b.empty() && b.back()==0) b.pop_back();int n=a.size();int m=b.size();if(n<m) return {};reverse(a.begin(),a.end());reverse(b.begin(),b.end());vector<int> ans=a*inv(b,n-m+1);while(ans.size()>n-m+1) ans.pop_back();reverse(ans.begin(),ans.end());while(!ans.empty() && ans.back()==0) ans.pop_back();return ans;}vector<int> operator%(vector<int> a,vector <int> b){vector<int> ans=a-b*(a/b);while(!ans.empty() && ans.back()==0) ans.pop_back(); return ans;}const int maxn=1e5+5;int fact[maxn];int invf[maxn];int po2[maxn];int dp[maxn];int cn[maxn];int cur[maxn];void go(int l,int r){if(r-l==1){cur[l]*=fact[l];cur[l]%=p;if(cn[l]) debug(l,cur[l]);dp[l]=cur[l]*(po2[cn[l]]-1);dp[l]%=p;if(cn[l]) debug(dp[l]);return;}int m=(l+r)/2;go(l,m);vector<int> v;for(int i=l;i<m;++i) v.app((dp[i]*invf[i])%p);vector<int> v2;for(int i=0;i<r-l;++i) {v2.app(invf[i]);}vector<int> c=v*v2;c.resize(r-l);for(int i=m-l;i<r-l;++i) {cur[i+l]+=c[i];cur[i+l]%=p;}go(m,r);}int32_t main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);po2[0]=1;for(int i=1;i<maxn;++i) {po2[i]=(po2[i-1]*2)%p;}fact[0]=1;for(int i=1;i<maxn;++i) {fact[i]=(fact[i-1]*i)%p;} for(int i=0;i<maxn;++i) {invf[i]=inv(fact[i]);}for(int i=0;i<maxn;++i) cur[i]=invf[i];int n;cin>>n;int a[n];for(int i=0;i<n;++i) {cin>>a[i];cn[a[i]]++;}go(0,maxn);cout<<(accumulate(dp,dp+maxn,0LL)%p+p)%p;return 0;}