結果

問題 No.2633 Subsequence Combination Score
ユーザー maksimmaksim
提出日時 2024-02-16 22:28:01
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 348 ms
46,840 KB
testcase_01 AC 345 ms
47,740 KB
testcase_02 AC 351 ms
47,344 KB
testcase_03 AC 353 ms
47,660 KB
testcase_04 AC 345 ms
47,764 KB
testcase_05 AC 352 ms
47,772 KB
testcase_06 AC 353 ms
47,788 KB
testcase_07 AC 346 ms
47,772 KB
testcase_08 AC 374 ms
47,984 KB
testcase_09 AC 359 ms
48,532 KB
testcase_10 AC 349 ms
48,476 KB
testcase_11 AC 353 ms
48,492 KB
testcase_12 AC 351 ms
48,464 KB
testcase_13 AC 351 ms
48,592 KB
testcase_14 AC 354 ms
48,464 KB
testcase_15 AC 360 ms
48,516 KB
testcase_16 AC 356 ms
48,344 KB
testcase_17 AC 350 ms
48,456 KB
testcase_18 AC 366 ms
48,456 KB
testcase_19 AC 357 ms
48,532 KB
testcase_20 AC 362 ms
48,516 KB
testcase_21 AC 361 ms
48,480 KB
testcase_22 AC 362 ms
48,440 KB
testcase_23 AC 363 ms
48,404 KB
testcase_24 AC 362 ms
48,316 KB
testcase_25 AC 363 ms
48,320 KB
testcase_26 AC 363 ms
48,228 KB
testcase_27 AC 360 ms
48,312 KB
testcase_28 AC 360 ms
48,284 KB
testcase_29 AC 352 ms
47,748 KB
testcase_30 AC 370 ms
47,072 KB
testcase_31 AC 351 ms
46,912 KB
testcase_32 AC 354 ms
47,252 KB
testcase_33 AC 361 ms
48,532 KB
testcase_34 AC 364 ms
48,656 KB
testcase_35 AC 369 ms
48,400 KB
testcase_36 AC 359 ms
48,656 KB
testcase_37 AC 359 ms
48,524 KB
testcase_38 AC 358 ms
48,512 KB
testcase_39 AC 350 ms
48,504 KB
testcase_40 AC 348 ms
48,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 // LOCAL
typedef 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;
}
0