結果
問題 | No.2633 Subsequence Combination Score |
ユーザー |
👑 ![]() |
提出日時 | 2024-02-13 00:50:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 249 ms / 2,000 ms |
コード長 | 1,027 bytes |
コンパイル時間 | 4,665 ms |
コンパイル使用メモリ | 259,112 KB |
最終ジャッジ日時 | 2025-02-19 05:49:13 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using mint=modint998244353; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) int main() { int L=(1<<17); int N; cin>>N; vector<int> A(L); rep(i,0,N){ int a; cin>>a; A[a]++; } vector<mint> dp(L); vector<mint> fact(L,1),fact_inv(L,1); rep(i,1,L) fact[i]=fact[i-1]*i; fact_inv[L-1]=fact[L-1].inv(); for(int i=L-1;i>0;i--) fact_inv[i-1]=fact_inv[i]*i; mint ans=0; auto f=[&](auto self,int l,int r) -> void { if(l+1==r){ dp[l]+=fact_inv[l]; dp[l]*=(mint(2).pow(A[l])-1); ans+=dp[l]*fact[l]; return; } int m=(l+r)/2; self(self,l,m); vector<mint> p(m-l),q(r-l); rep(i,l,m) p[i-l]=dp[i]; rep(i,0,r-l) q[i]=fact_inv[i]; p=convolution(p,q); rep(i,m,r) dp[i]+=p[i-l]; self(self,m,r); }; f(f,0,L); cout<<ans.val()<<"\n"; }