QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417677 | #8721. 括号序列 | Afterlife | AC ✓ | 1940ms | 37220kb | C++17 | 5.8kb | 2024-05-22 20:42:30 | 2024-05-22 20:42:42 |
Judging History
answer
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353,P=998244353,N=1<<20;
using poly =vector<int>;
inline int qpow(int x,int y=P-2)
{
int ans=1;
for(;y;y>>=1,x=x*x%P)
if(y&1)
ans=ans*x%P;
return ans;
}
poly operator *(poly v, const int &a) {
for(auto &x: v)
x = x * a % P;
return v;
}
poly operator +(poly v, poly a) {
int z = max(v.size(), a.size());
v.resize(z), a.resize(z);
for(int i = 0; i < z; i += 1)
v[i] = (v[i] + a[i] >= P ? v[i] + a[i] - P : v[i] + a[i]);
return v;
}
namespace Core
{
int a[N],b[N],w[N],rev[N];
inline void NTT(int *a,int len)
{
for(int i=1;i<len;++i)
if(i>rev[i])
swap(a[i],a[rev[i]]);
for(int d=1;d<len;d<<=1)
for(int m=d<<1,i=0;i<len;i+=m)
for(int j=0;j<d;++j)
{
int x=a[i+j],y=a[i+j+d]*w[len/m*j]%P;
a[i+j]=(x+y>=P?x+y-P:x+y);
a[i+j+d]=(x-y<0?x-y+P:x-y);
}
}
}
inline poly operator*(const poly &va,const poly &vb)
{
if(va.size() + vb.size() <= 32) {
poly c(va.size() + vb.size() - 1);
for(int i = 0; i < va.size(); i += 1) {
for(int j = 0; j < vb.size(); j += 1) {
c[i + j] += va[i] * vb[j];
if(!(i & 7))
c[i + j] %= P;
}
}
for(auto &x: c)
x %= P;
return c;
}
using namespace Core;
int len=1;
while(len<(int)va.size()+(int)vb.size()-1)
len<<=1;
for(int i=0;i<len;++i)
a[i]=(i<(int)va.size()?va[i]:0),
b[i]=(i<(int)vb.size()?vb[i]:0);
for(int i=1;i<len;++i)
rev[i]=rev[i>>1]>>1|(i&1?len>>1:0);
w[0]=1;
w[1]=qpow(3,(P-1)/len);
for(int i=2;i<len;++i)
w[i]=w[i-1]*w[1]%P;
NTT(a,len);
NTT(b,len);
for(int i=0;i<len;++i)
a[i]=a[i]*b[i]%P;
reverse(a+1,a+len);
NTT(a,len);
poly c(va.size()+vb.size()-1);
for(int i=0,invlen=qpow(len);i<(int)c.size();++i)
c[i]=a[i]*invlen%P;
return c;
}
inline int inv(int x){return qpow(x,mod-2);}
int t[250005] , rt[250005] , iv[250005];
poly f , g;
void solve(int l,int r) {
// printf("ON %d %d\n" , l , r);
if(l == r) {
if(l) f[l] = f[l] * iv[l] % mod ;
return ;
}
int md = (l + r >> 1);
solve(l , md) ;
if(l == 0) {
poly a(f.begin() , f.begin() + md + 1) ;
poly b = a * a;
b.resize(r) ;
poly c = b * a;
for(int i = md + 1 ; i <= r;i++) {
f[i] = (f[i] + b[i - 1] + c[i - 1]) %mod;
}
}
else {
poly a(f.begin() + l , f.begin() + md + 1 ) ;
poly b(f.begin() , f.begin() + r - l + 1) ;
poly d = a * b; d.resize(r - l);
poly c = d * b;
assert(r - l + 1 <= md) ;
// printf("AS %d\n",a.size()) ;
// printf("A %d %d : %d\n",l,r,md);
for(int i = md + 1 ; i <= r ;i++) {
// printf("%d %d %d\n",i,1LL * f[i] * t[i - 1] % mod, 1LL * c[i-1 - l] * t[i - 1] % mod) ;
f[i] = (f[i] + 3 * c[i - 1 - l] + 2 * d[i - l - 1]) % mod;
}
}
solve(md + 1 , r);
}
void solve2(int l,int r) {
if(l == r) {
if(l) g[l] = g[l] * iv[l] % mod;
return ;
}
int md = (l + r >> 1);
solve2(l , md) ;
if(l == 0) {
poly a(g.begin() , g.begin() + md + 1) ;
poly b(f.begin() , f.begin() + md + 1) ;
b = a * b;
b.resize(r);
b = b * a;
for(int i = md + 1;i <= r;i++) {
g[i] = (g[i] + b[i - 1]) % mod;
}
}
else {
poly a(g.begin() , g.begin() + r - l + 1);
poly b(f.begin() , f.begin() + r - l + 1);
poly c(g.begin() + l , g.begin() + md + 1) ;
poly d(f.begin() + l , f.begin() + md + 1);
// printf("IN %d %d\n",l,r);
poly e = c * b* 2 + d * a;
e.resize(r - l) ;
e = e * a;
for(int i = md + 1;i <= r;i++) {
g[i] = (g[i] + e[i - l - 1]) % mod;
}
}
solve2(md + 1 , r);
}
signed main() {
int n ; cin >> n;
t[0] =1 ; rt[0] = 1;
for(int i = 1;i <= n + 2;i++) {
t[i] = t[i - 1] * i % mod ;
if(i == 1) iv[i] = 1;
else iv[i] = (mod - mod / i) * iv[mod % i] % mod ;
rt[i] = rt[i - 1] * iv[i] % mod;
}
f.resize(n + 1); f[0] = 1;
g.resize(n + 1) ; g[0] = 1;
solve(0 , n);
solve2(0 , n);
cout << g[n]*t[n] % mod << '\n';
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3512kb
input:
3
output:
28
result:
ok 1 number(s): "28"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
4
output:
282
result:
ok 1 number(s): "282"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
5
output:
3718
result:
ok 1 number(s): "3718"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
6
output:
60694
result:
ok 1 number(s): "60694"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
7
output:
1182522
result:
ok 1 number(s): "1182522"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
8
output:
26791738
result:
ok 1 number(s): "26791738"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
9
output:
692310518
result:
ok 1 number(s): "692310518"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3436kb
input:
10
output:
135061370
result:
ok 1 number(s): "135061370"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
100
output:
423669705
result:
ok 1 number(s): "423669705"
Test #12:
score: 0
Accepted
time: 4ms
memory: 3916kb
input:
1234
output:
878522960
result:
ok 1 number(s): "878522960"
Test #13:
score: 0
Accepted
time: 349ms
memory: 11248kb
input:
54321
output:
827950477
result:
ok 1 number(s): "827950477"
Test #14:
score: 0
Accepted
time: 401ms
memory: 11900kb
input:
65536
output:
380835743
result:
ok 1 number(s): "380835743"
Test #15:
score: 0
Accepted
time: 886ms
memory: 20636kb
input:
131072
output:
842796122
result:
ok 1 number(s): "842796122"
Test #16:
score: 0
Accepted
time: 831ms
memory: 20744kb
input:
131071
output:
981021531
result:
ok 1 number(s): "981021531"
Test #17:
score: 0
Accepted
time: 844ms
memory: 20756kb
input:
131070
output:
480197639
result:
ok 1 number(s): "480197639"
Test #18:
score: 0
Accepted
time: 905ms
memory: 20676kb
input:
131074
output:
383000585
result:
ok 1 number(s): "383000585"
Test #19:
score: 0
Accepted
time: 869ms
memory: 20700kb
input:
131073
output:
316664839
result:
ok 1 number(s): "316664839"
Test #20:
score: 0
Accepted
time: 1929ms
memory: 37220kb
input:
250000
output:
119658643
result:
ok 1 number(s): "119658643"
Test #21:
score: 0
Accepted
time: 1921ms
memory: 37040kb
input:
249999
output:
78110138
result:
ok 1 number(s): "78110138"
Test #22:
score: 0
Accepted
time: 1940ms
memory: 37056kb
input:
249998
output:
297253469
result:
ok 1 number(s): "297253469"
Extra Test:
score: 0
Extra Test Passed