結果

問題 No.2605 Pickup Parentheses
ユーザー TairitsuMeow
提出日時 2024-01-12 22:43:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 266 ms / 2,000 ms
コード長 2,861 bytes
コンパイル時間 3,747 ms
コンパイル使用メモリ 246,268 KB
実行使用メモリ 27,280 KB
最終ジャッジ日時 2024-09-30 06:27:57
合計ジャッジ時間 9,363 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 68
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// Problem: No.2605 Pickup Parentheses
// Contest: yukicoder
// URL: https://yukicoder.me/problems/no/2605
// Memory Limit: 512 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
#include<atcoder/all>
#define debug(x) cerr<<(#x)<<" "<<(x)<<endl
using mint=atcoder::modint998244353;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe; 
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=2e6+9,Mod=998244353,G=3,IG=332748118;
ll n,m,a[N],fac[N],ifac[N],r[N],cat[N];
ll pw(ll x,ll p){
    ll res=1;
    while(p){
        if(p&1)res=res*x%Mod;
        x=x*x%Mod;
        p>>=1;
    }
    return res;
}
void NTT(vector<ll>&a,ll n,ll sgn){
    rep(i,0,n-1){
        if(i<r[i])swap(a[i],a[r[i]]);
    }
    for(ll mid=1;mid<n;mid*=2){
        ll Wn=pw(sgn==1?G:IG,(Mod-1)/(mid<<1));
        for(ll R=mid<<1,j=0;j<n;j+=R){
            ll w=1;
            for(ll k=0;k<mid;k++,w=w*Wn%Mod){
                ll x=a[j+k],y=a[j+k+mid]*w%Mod;
                a[j+k]=(x+y)%Mod,a[j+k+mid]=(x-y+Mod)%Mod;
            }
        }
    }
    if(sgn==-1){
        ll inv=pw(n,Mod-2);
        rep(i,0,n-1)a[i]=a[i]*inv%Mod;
    }
}
void MUL(vector<ll>&f,vector<ll>&g,ll n,ll m){
    ll mxlen=n+m;
    ll p=1,c=0;
    while(p<=mxlen)p<<=1,c++;
    f.resize(p),g.resize(p);
    r[0]=0;
    rep(i,1,p-1)r[i]=(r[i>>1]>>1)|((i&1)<<(c-1));
    NTT(f,p,1),NTT(g,p,1);
    rep(i,0,p-1)f[i]=f[i]*g[i]%Mod;
    NTT(f,p,-1);
    f.resize(n+m-1);
}
vector<mint> work(ll l,ll r){
    if(l==r){
        vector<mint>vec(a[l]+1,0);
        vec[0]=1;
        if(a[l]%2==0)vec[a[l]]=(Mod-cat[a[l]/2])%Mod;
        else {
            vec.clear();
            vec.push_back(1);
        }
        return vec;
    }
    ll mid=(l+r)>>1;
    vector<mint>lf=work(l,mid);
    vector<mint>rg=work(mid+1,r);
    lf=atcoder::convolution(lf,rg);
    return lf;
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    n=read(),m=read();
    if(n&1)return puts("0"),0;
    queue<vector<mint> >q;
    
    fac[0]=1;
    rep(i,1,n*2)fac[i]=fac[i-1]*i%Mod;
    ifac[n*2]=pw(fac[n*2],Mod-2);
    per(i,n*2-1,0)ifac[i]=ifac[i+1]*(i+1)%Mod;
    cat[0]=1;
    rep(i,1,n)cat[i]=fac[i*2]*ifac[i]%Mod*ifac[i]%Mod*pw(i+1,Mod-2)%Mod;
    if(m==0){
      cout<<cat[n/2];
      return 0;
    }
    rep(i,1,m){
        ll l=read(),r=read();
        a[i]=r-l+1;
        if(a[i]%2==0){
        vector<mint>vec(a[i]+1,0);
          vec[0]=1;
          vec[a[i]]=(Mod-cat[a[i]/2])%Mod;
        q.push(vec);
        }
        else {
            vector<mint>vec(1,0);
            vec[0]=1;
        q.push(vec);
        }
    }
while(q.size()>1){
        auto f=q.front();q.pop();
        auto g=q.front();q.pop();
        q.push(atcoder::convolution(f,g));
    }
    auto f=q.front();
    mint ans=0;
    rep(i,0,min((ll)f.size()-1,n)){
      if((n-i)%2==0)ans=(ans+mint(cat[(n-i)/2])*f[i]);
    }
    write(ans.val());
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0