QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #417984 | #8721. 括号序列 | grass8cow | TL | 1154ms | 12068kb | C++17 | 2.4kb | 2024-05-23 08:34:27 | 2024-05-23 08:34:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,G=3,GI=(mod+1)/3;
int qpow(int a,int b){
int c=1;
for(;b;b>>=1){
if(b&1)c=1ll*a*c%mod;
a=1ll*a*a%mod;
}
return c;
}
int f[251000],jc[251000],ij[250100],n,g[250100],inv[250100];
int C(int a,int b){
return 1ll*jc[a]*ij[b]%mod*ij[a-b]%mod;
}
int L,lb[1<<20];
void init(int n){
L=1;while(L<=n)L<<=1;
for(int i=1;i<L;i++)lb[i]=(lb[i>>1]>>1)|((i&1)?(L>>1):0);
}
void NTT(int *a,int fl){
for(int i=0;i<L;i++)if(i<lb[i])swap(a[i],a[lb[i]]);
for(int o=1;o<L;o<<=1){
int Wn=qpow(fl?G:GI,(mod-1)/(o<<1));
for(int i=0;i<L;i+=(o<<1))for(int j=0,w=1;j<o;j++,w=1ll*w*Wn%mod){
int x=a[i+j],y=1ll*a[i+j+o]*w%mod;
a[i+j]=(x+y)%mod,a[i+j+o]=(x-y)%mod;
}
}
if(!fl){
int I=qpow(L,mod-2);
for(int i=0;i<L;i++)a[i]=1ll*a[i]*I%mod;
}
}
int p[1<<20],q[1<<20];
void cdq(int l,int r){
if(l==r){if(!l)return;(f[l]+=1ll*g[l]*inv[l]%mod)%=mod;return;}
int mi=(l+r)>>1;
cdq(l,mi);init(r-l+mi-l+3);
//part1
for(int i=0;i<L;i++)p[i]=q[i]=0;
for(int i=l;i<=mi;i++)p[i-l]=f[i];
for(int i=0;i<=mi&&i<=r-l-1;i++)q[i]=g[i];
NTT(p,1),NTT(q,1);for(int i=0;i<L;i++)p[i]=1ll*p[i]*q[i]%mod;
NTT(p,0);
for(int i=mi;i<r;i++)(g[i+1]+=p[i-l])%=mod;
//---
for(int i=0;i<L;i++)p[i]=q[i]=0;
for(int i=l;i<=mi;i++)p[i-l]=g[i];
for(int i=0;i<l&&i<=r-l-1;i++)q[i]=f[i];
NTT(p,1),NTT(q,1);for(int i=0;i<L;i++)p[i]=1ll*p[i]*q[i]%mod;
NTT(p,0);
for(int i=mi;i<r;i++)(g[i+1]+=p[i-l])%=mod;
//---
//part2
for(int i=0;i<L;i++)p[i]=q[i]=0;
for(int i=max(l,1);i<=mi;i++)p[i-l]=f[i];
for(int i=1;i<=mi&&i<=r-l;i++)q[i]=1ll*inv[i]*g[i]%mod;
NTT(p,1),NTT(q,1);for(int i=0;i<L;i++)p[i]=1ll*p[i]*q[i]%mod;
NTT(p,0);
for(int i=mi+1;i<=r;i++)(f[i]+=p[i-l])%=mod;
//---
for(int i=0;i<L;i++)p[i]=q[i]=0;
for(int i=max(l,1);i<=mi;i++)p[i-l]=1ll*inv[i]*g[i]%mod;
for(int i=1;i<l&&i<=r-l;i++)q[i]=f[i];
NTT(p,1),NTT(q,1);for(int i=0;i<L;i++)p[i]=1ll*p[i]*q[i]%mod;
NTT(p,0);
for(int i=mi+1;i<=r;i++)(f[i]+=p[i-l])%=mod;
cdq(mi+1,r);
}
int main(){
jc[0]=ij[0]=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)jc[i]=1ll*i*jc[i-1]%mod,ij[i]=qpow(jc[i],mod-2),
inv[i]=1ll*jc[i-1]*ij[i]%mod;
f[0]=g[0]=1;
cdq(0,n);
return printf("%d",(1ll*f[n]*jc[n]%mod+mod)%mod),0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 12068kb
input:
3
output:
28
result:
ok 1 number(s): "28"
Test #2:
score: 0
Accepted
time: 0ms
memory: 10132kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 10080kb
input:
2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 9948kb
input:
4
output:
282
result:
ok 1 number(s): "282"
Test #5:
score: 0
Accepted
time: 2ms
memory: 11988kb
input:
5
output:
3718
result:
ok 1 number(s): "3718"
Test #6:
score: 0
Accepted
time: 0ms
memory: 9992kb
input:
6
output:
60694
result:
ok 1 number(s): "60694"
Test #7:
score: 0
Accepted
time: 2ms
memory: 12052kb
input:
7
output:
1182522
result:
ok 1 number(s): "1182522"
Test #8:
score: 0
Accepted
time: 0ms
memory: 10068kb
input:
8
output:
26791738
result:
ok 1 number(s): "26791738"
Test #9:
score: 0
Accepted
time: 0ms
memory: 12044kb
input:
9
output:
692310518
result:
ok 1 number(s): "692310518"
Test #10:
score: 0
Accepted
time: 2ms
memory: 10124kb
input:
10
output:
135061370
result:
ok 1 number(s): "135061370"
Test #11:
score: 0
Accepted
time: 0ms
memory: 12036kb
input:
100
output:
423669705
result:
ok 1 number(s): "423669705"
Test #12:
score: 0
Accepted
time: 10ms
memory: 10152kb
input:
1234
output:
878522960
result:
ok 1 number(s): "878522960"
Test #13:
score: 0
Accepted
time: 965ms
memory: 11208kb
input:
54321
output:
827950477
result:
ok 1 number(s): "827950477"
Test #14:
score: 0
Accepted
time: 1154ms
memory: 11296kb
input:
65536
output:
380835743
result:
ok 1 number(s): "380835743"
Test #15:
score: -100
Time Limit Exceeded
input:
131072