結果
問題 | No.2605 Pickup Parentheses |
ユーザー |
![]() |
提出日時 | 2024-01-12 22:52:46 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,489 bytes |
コンパイル時間 | 4,322 ms |
コンパイル使用メモリ | 274,992 KB |
実行使用メモリ | 8,992 KB |
最終ジャッジ日時 | 2024-09-27 23:40:00 |
合計ジャッジ時間 | 12,703 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 WA * 18 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)#define rep2ll(i,m,n) for(ll (i)=(m);(i)<(n);(i)++)#define ALL(obj) (obj).begin(), (obj).end()#define rALL(obj) (obj).rbegin(), (obj).rend()using namespace std;using ll = long long;using P = pair<ll,ll>;using mint = atcoder::modint998244353;using VL = vector<ll>;using VVL = vector<VL>;using VVVL = vector<VVL>;using VM = vector<mint>;using VVM = vector<VM>;using VVVM = vector<VVM>;using VD = vector<double>;using VVD = vector<VD>;using VVVD = vector<VVD>;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }template< typename T >struct Combination {vector< T > _fact, _rfact, _inv;Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {_fact[0] = _rfact[sz] = _inv[0] = 1;for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;_rfact[sz] /= _fact[sz];for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];}inline T fact(int k) const { return _fact[k]; }inline T rfact(int k) const { return _rfact[k]; }inline T inv(int k) const { return _inv[k]; }T P(int n, int r) const {if(r < 0 || n < r) return 0;return fact(n) * rfact(n - r);}T C(int p, int q) const {if(q < 0 || p < q) return 0;return fact(p) * rfact(q) * rfact(p - q);}T H(int n, int r) const {if(n < 0 || r < 0) return (0);return r == 0 ? 1 : C(n + r - 1, r);}};int main(){ios::sync_with_stdio(false);cin.tie(0);ll n, m; cin>>n>>m;VL cnt(n/2+1, 0);bool zero = n%2;rep(i,m){ll l, r; cin>>l>>r; l--;zero |= (r-l)%2;cnt[(r-l)/2]++;}if(zero){cout<<0;return 0;}n /= 2;vector<P> arr;rep(i,n+1) if(cnt[i]) arr.push_back({i, cnt[i]});Combination<mint> c(2*n+1);VM cata(n+1, 0);rep(i,n+1) cata[i] = c.fact(2*i) * c.rfact(i+1) * c.rfact(i);VM dp(1, 1);for(auto [x, y]: arr){VM dp_(x*y+1, 0);rep(j, y+1) dp_[x*j] = cata[x].pow(j) * c.C(y, j) * (1-j%2*2);dp = atcoder::convolution(dp, dp_);}mint ans = 0;rep(i,dp.size()) ans += dp[i] * cata[n-i];cout<<ans.val();return 0;}