結果
問題 | No.2605 Pickup Parentheses |
ユーザー |
![]() |
提出日時 | 2024-01-14 09:05:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 137 ms / 2,000 ms |
コード長 | 1,067 bytes |
コンパイル時間 | 4,528 ms |
コンパイル使用メモリ | 233,928 KB |
最終ジャッジ日時 | 2025-02-18 20:05:33 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 68 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/modint> #include<atcoder/convolution> using namespace std; using mint=atcoder::modint998244353; const int mod=mint::mod(); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N,M; cin>>N>>M; if(N&1){cout<<0<<endl;return 0;} N/=2; vector<mint>inv(N+2),C(N+1); inv[1]=1; for(int i=2;i<=N+1;i++)inv[i]=mod-inv[mod%i]*(mod/i); C[0]=1; for(int i=0;i<N;i++)C[i+1]=2*(2*i+1)*C[i]/(i+2); vector<vector<mint>>F; for(;M--;) { int l,r; cin>>l>>r; int a=r-l+1; if(a&1)continue; a/=2; vector<mint>f(a+1); f[0]=1; f[a]=-C[a]; F.emplace_back(f); } auto dfs=[&](auto& dfs, int l, int r)->vector<mint> { if(F.empty())return {1}; if(l+1==r)return F[l]; int m=(r+l)/2; return atcoder::convolution(dfs(dfs,l,m),dfs(dfs,m,r)); }; auto f=dfs(dfs,0,F.size()); mint ans=0; for(int i=0;i<f.size();i++)ans+=f[i]*C[N-i]; cout << ans.val() << endl; }