QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#417677#8721. 括号序列AfterlifeAC ✓1940ms37220kbC++175.8kb2024-05-22 20:42:302024-05-22 20:42:42

Judging History

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

  • [2024-05-22 20:42:42]
  • 评测
  • 测评结果:AC
  • 用时:1940ms
  • 内存:37220kb
  • [2024-05-22 20:42:30]
  • 提交

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