結果
問題 | No.2633 Subsequence Combination Score |
ユーザー |
![]() |
提出日時 | 2024-02-16 23:04:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 257 ms / 2,000 ms |
コード長 | 1,515 bytes |
コンパイル時間 | 4,417 ms |
コンパイル使用メモリ | 262,284 KB |
最終ジャッジ日時 | 2025-02-19 14:39:06 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 struct combi{ deque<mint> kaijou; deque<mint> kaijou_; combi(int n){ kaijou.push_back(1); for(int i=1;i<=n;i++){ kaijou.push_back(kaijou[i-1]*i); } mint b=kaijou[n].inv(); kaijou_.push_front(b); for(int i=1;i<=n;i++){ int k=n+1-i; kaijou_.push_front(kaijou_[0]*k); } } mint combination(int n,int r){ if(r>n)return 0; mint a = kaijou[n]*kaijou_[r]; a *= kaijou_[n-r]; return a; } mint junretsu(int a,int b){ mint x = kaijou_[a]*kaijou_[b]; x *= kaijou[a+b]; return x; } mint catalan(int n){ return combination(2*n,n)/(n+1); } }; combi C(200005); int cnt[100005]; mint dp[100005]; void dfs(int l,int r){ //cout<<l<<' '<<r<<endl; if(r-l==0)return; if(r-l==1){ dp[l]++; dp[l] *= mint(2).pow(cnt[l])-1; return ; } int m = (l+r)/2; dfs(l,m); vector<mint> x(r-l+5); rep(i,x.size())x[i] = C.kaijou_[i]; vector<mint> y(r-l+1); for(int i=l;i<m;i++){ y[i-l] = dp[i] * C.kaijou_[i]; } x = convolution(x,y); rep(i,x.size()){ int pp = i; pp += l; if(pp>=m && pp<r)dp[pp] += x[i] * C.kaijou[pp]; } dfs(m,r); } int main(){ int n; cin>>n; rep(i,n){ int a; cin>>a; cnt[a]++; } dfs(0,100001); mint ans =0; rep(i,100005)ans += dp[i]; cout<<ans.val()<<endl; return 0; }