QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#418989	#8721. 括号序列	light_ink_dots	TL	1257ms	531896kb	C++14	6.7kb	2024-05-23 16:50:10	2024-05-23 16:50:12

Judging History

你现在查看的是最新测评结果

[2024-05-23 16:50:12]
评测

测评结果：TL
用时：1257ms
内存：531896kb

查看

[2024-05-23 16:50:10]
提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
#define int long long
const int mod= 998244353;
int siz;
namespace Poly{
int w[2000000],*rev[20],F[500000],Finv[500000],Inv[500000];
inline int qpow(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;b>>=1;
    }return ret;
}
inline void init(){
    int n=400000;
    F[0]=Finv[0]=1;
    for(int i=1;i<=n;i++) F[i]=F[i-1]*i%mod;
    Finv[n]=qpow(F[n],mod-2);
    for(int i=n-1;i>=0;i--) Finv[i]=Finv[i+1]*(i+1)%mod;
    for(int i=1;i<=n;i++) Inv[i]=F[i-1]*Finv[i]%mod;
    for(int mid=1;mid<(1<<20);mid<<=1){
        int wn=qpow(3,(mod-1)/(mid*2));
        w[mid]=1;
        for(int k=1;k<mid;k++) w[mid+k]=w[mid+k-1]*wn%mod;
    }
}
inline void upd(int &x){
    if(x>=mod) x-=mod;
    if(x<0) x+=mod;
}

struct poly{
    vector<int>a;
    inline int size()const{return (int)(a.size())-1;}
    inline void resize(int n){a.resize(n+1);}
    void reduce(int n){
        if(size()>n) resize(n);
    }
    poly(){}
    poly(int n){resize(n);}
    poly(const vector<int>&_a){a=_a;}
    inline int&operator[](int n){return a[n];}
    void dif(int lim){
        a.resize(lim);
        for(int mid=1;mid<lim;mid<<=1){
            for(int j=0;j<lim;j+=(mid<<1)){
                int x=a[j],y=a[j+mid];
                upd(a[j]=x+y);
                upd(a[j+mid]=x-y);
                for(int k=1;k<mid;k++){
                    int x=a[j+k],y=a[j+k+mid]*(mod-w[2*mid-k])%mod;
                    upd(a[j+k]=x+y);
                    upd(a[j+k+mid]=x-y);
                }
            }
        }
        int inv=qpow(lim,mod-2);
        for(int i=0;i<lim;i++)a[i]=a[i]*inv%mod;
    }
    void dit(int lim){
        a.resize(lim);        
        for(int mid=(lim>>1);mid>=1;mid>>=1){
            for(int j=0;j<lim;j+=(mid<<1)){
                for(int k=0;k<mid;k++){
                    int x=a[j+k],y=a[j+k+mid];
                    upd(a[j+k]=x+y);
                    (a[j+k+mid]=(x-y)*w[mid+k])%=mod;
                }
            }
        }
    }
    inline poly operator *(const poly &b)const{
        poly c=(*this),d=b;
        if(b.size()==-1||(c.size())==-1) return poly();
        int len=c.size()+d.size();
        int lim=1;while(lim<=len) lim<<=1;
        siz+=lim;
        c.dit(lim),d.dit(lim);
        for(int i=0;i<lim;i++) c[i]=c[i]*d[i]%mod;
        c.dif(lim);c.resize(len);
        return c;
    }
    inline poly operator +(const poly &b){
        poly c=(*this),d=b;
        int len=max(c.size(),d.size());
        c.resize(len);d.resize(len);
        for(int i=0;i<=len;i++) upd(c[i]+=d[i]);
        return c;
    }
    inline poly operator -(const poly &b){
        poly c=(*this),d=b;
        int len=max(c.size(),d.size());
        c.resize(len);d.resize(len);
        for(int i=0;i<=len;i++) upd(c[i]-=d[i]);
        return c;
    }
    inline poly inv(int lim){
        if(lim==1){
            return poly(vector<int>{qpow(a[0],mod-2)});
        }
        int len=(lim+1)/2;
        poly h=(*this);h.resize(lim-1);
        poly f0=h.inv(len),res=f0+f0-(f0*f0)*h;
        res.resize(lim-1);
        return res;
    }
    inline poly ln(int lim){
        poly r=inv(lim),ans(lim-1),d=(*this);
        d.resize(lim);
        for(int i=0;i<lim;i++) d[i]=d[i+1]*(i+1)%mod;
        r=r*d;
        for(int i=1;i<lim;i++) ans[i]=r[i-1]*Inv[i]%mod;
        return ans;
    }
    inline poly exp(int lim){
        if(lim==1){
            return poly(vector<int>{1});
        }
        int len=(lim+1)/2;
        poly h=(*this);h.resize(lim-1);
        poly f0=h.exp(len);
        poly res=f0-(f0.ln(lim)-h)*f0;
        res.resize(lim-1);
        return res;
    }
    poly shift(int x){
        int n=size();
        poly f=(*this),g(n);
        int prod=1;
        for(int i=0;i<=n;i++) {
            f[i]=f[i]*F[i]%mod;
            g[i]=prod*Finv[i]%mod;prod=prod*x%mod;
        }
        reverse(f.a.begin(),f.a.end());
        f=f*g;
        f.resize(n);
        reverse(f.a.begin(),f.a.end());
        for(int i=0;i<=n;i++) f[i]=f[i]*Finv[i]%mod;
        // cerr<<"?? "<<n<<" "<<f.size()<<endl;
        return f;
    }
};
inline int comb(int n,int m){
    if(n<m||m<0) return 0;
    return F[n]*Finv[n-m]%mod*Finv[m]%mod;
}
}
int z[3000000];

struct Mat{
    Poly::poly a,b,c,d,e,f;
};

int n;
Mat operator *(Mat &f,Mat &g){
    Mat h;
    int len=max({f.a.size(),f.b.size(),f.c.size(),f.d.size(),f.e.size(),f.f.size()})*2;
    int lim=1;
    while(lim<=len) lim<<=1;
    siz+=lim;
    f.a.dit(lim);
    f.b.dit(lim);
    f.c.dit(lim);
    f.d.dit(lim);
    f.e.dit(lim);
    f.f.dit(lim);
    
    g.a.dit(lim);
    g.b.dit(lim);
    g.c.dit(lim);
    g.d.dit(lim);
    g.e.dit(lim);
    g.f.dit(lim);
    h.a.resize(lim-1);
    h.b.resize(lim-1);
    h.c.resize(lim-1);
    h.d.resize(lim-1);
    h.e.resize(lim-1);
    h.f.resize(lim-1);
    for(int i=0;i<lim;i++) h.a[i]=(f.a[i]*g.a[i]+f.b[i]*g.c[i])%mod;
    for(int i=0;i<lim;i++) h.b[i]=(f.a[i]*g.b[i]+f.b[i]*g.d[i])%mod;
    for(int i=0;i<lim;i++) h.c[i]=(f.c[i]*g.a[i]+f.d[i]*g.c[i])%mod;
    for(int i=0;i<lim;i++) h.d[i]=(f.c[i]*g.b[i]+f.d[i]*g.d[i])%mod;
    for(int i=0;i<lim;i++) h.e[i]=(f.e[i]*g.a[i]+f.f[i]*g.c[i]+g.e[i])%mod;
    for(int i=0;i<lim;i++) h.f[i]=(f.e[i]*g.b[i]+f.f[i]*g.d[i]+g.f[i])%mod;
    h.a.dif(lim);
    h.b.dif(lim);
    h.c.dif(lim);
    h.d.dif(lim);
    h.e.dif(lim);
    h.f.dif(lim);
    h.a.reduce(n);
    h.b.reduce(n);
    h.c.reduce(n);
    h.d.reduce(n);
    h.e.reduce(n);
    h.f.reduce(n);
    return h;   
}
Mat h[600000];
Mat f[1100000];
void calc(int p,int l,int r){
    if(l==r){
        f[p]=h[l];
        return ;
    }int mid=l+r>>1;
    calc(p<<1,l,mid),calc(p<<1|1,mid+1,r);
    // if(l==2&&r==3){
        // for(int i=0;i<=f[p<<1].a.size();i++) cerr<<f[p<<1].a[i]<<" ";cerr<<endl;
        // for(int i=0;i<=f[p<<1|1].a.size();i++) cerr<<f[p<<1|1].a[i]<<" ";cerr<<endl;
    // }
    f[p]=f[p<<1|1]*f[p<<1];
    // cerr<<l<<" "<<r<<" : ";for(int i=0;i<=f[p].a.size();i++) cerr<<f[p].a[i]<<" ";cerr<<endl;
    
}
int32_t main(){
    Poly::init();
    Poly::poly g;
    cin>>n;
    for(int i=2;i<=2*n;i++){
        h[i].a=Poly::poly(vector<int>{0,(i-1)});
        h[i].b=Poly::poly(vector<int>{0,(i-2)});
        h[i].e=h[i].c=Poly::poly(vector<int>{1});
    }
    h[1].a=Poly::poly(vector<int>{0,1});
    calc(1,2,2*n);
    f[1]=f[1]*h[1];
    for(int i=1;i<=n;i++){
        z[i]=f[1].e[i];
    }
    g.resize(n);
    for(int i=0;i<=n;i++) g[i]=z[i]*Poly::Finv[i]%mod;
    auto tmp=(Poly::poly(vector<int>{1})-g).inv(n+1);
    cout<<tmp[n]*Poly::F[n]%mod<<endl;

    cerr<<siz<<endl;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 31ms

memory: 261024kb

input:

output:

result:

ok 1 number(s): "28"

Test #2:

score: 0

Accepted

time: 27ms

memory: 261332kb

input:

output:

result:

ok 1 number(s): "1"

Test #3:

score: 0

Accepted

time: 28ms

memory: 261520kb

input:

output:

result:

ok 1 number(s): "4"

Test #4:

score: 0

Accepted

time: 20ms

memory: 261448kb

input:

output:

result:

ok 1 number(s): "282"

Test #5:

score: 0

Accepted

time: 39ms

memory: 262252kb

input:

output:

result:

ok 1 number(s): "3718"

Test #6:

score: 0

Accepted

time: 35ms

memory: 262020kb

input:

output:

result:

ok 1 number(s): "60694"

Test #7:

score: 0

Accepted

time: 34ms

memory: 260900kb

input:

output:

result:

ok 1 number(s): "1182522"

Test #8:

score: 0

Accepted

time: 39ms

memory: 261888kb

input:

output:

26791738

result:

ok 1 number(s): "26791738"

Test #9:

score: 0

Accepted

time: 37ms

memory: 260560kb

input:

output:

692310518

result:

ok 1 number(s): "692310518"

Test #10:

score: 0

Accepted

time: 19ms

memory: 261212kb

input:

output:

135061370

result:

ok 1 number(s): "135061370"

Test #11:

score: 0

Accepted

time: 31ms

memory: 261680kb

input:

output:

423669705

result:

ok 1 number(s): "423669705"

Test #12:

score: 0

Accepted

time: 54ms

memory: 266312kb

input:

output:

878522960

result:

ok 1 number(s): "878522960"

Test #13:

score: 0

Accepted

time: 1257ms

memory: 531896kb

input:

output:

827950477

result:

ok 1 number(s): "827950477"

QOJ.ac

QOJ

Judging History

answer

Details

Test #1:

input:

output:

result:

Test #2:

input:

output:

result:

Test #3:

input:

output:

result:

Test #4:

input:

output:

result:

Test #5:

input:

output:

result:

Test #6:

input:

output:

result:

Test #7:

input:

output:

result:

Test #8:

input:

output:

result:

Test #9:

input:

output:

result:

Test #10:

input:

output:

result:

Test #11:

input:

output:

result:

Test #12:

input:

output:

result:

Test #13:

input:

output:

result:

Test #14:

input:

output:

result: