QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232358#7634. CardszhouhuanyiAC ✓6873ms177804kbC++234.9kb2023-10-30 11:38:452023-10-30 11:38:45

Judging History

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

  • [2023-10-30 11:38:45]
  • 评测
  • 测评结果:AC
  • 用时:6873ms
  • 内存:177804kb
  • [2023-10-30 11:38:45]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 100000
#define M 1048576
#define K 20
#define g 3
#define mod 998244353
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int n,m,length,ans=1,sx[N+1],num[M+1],F[N+1],A[M+1],B[M+1],rev[M+1],s[M+1],wn[K+1][M+1],wn2[K+1][M+1],dp[N+1][2],delta[N+1],delta2[N+1],delta3[N+1],delta4[N+1],delta5[N+1];
int fast_pow(int a,int b)
{
	int res=1,mul=a;
	while (b)
	{
		if (b&1) res=1ll*res*mul%mod;
		mul=1ll*mul*mul%mod,b>>=1;
	}
	return res;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
void Adder2(int &x,int d)
{
	x+=d;
	if (x<0) x+=mod;
	return;
}
void NTT(int limit,int *s,int type)
{
	int s1,s2;
	for (int i=1;i<limit;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?limit>>1:0);
	for (int i=1;i<limit;++i)
		if (rev[i]>i)
			swap(s[i],s[rev[i]]);
	if (type==1)
	{
		for (int i=2;i<=limit;i<<=1)
			for (int j=0;j+i-1<limit;j+=i)
				for (int k=j;k<j+(i>>1);++k)
					s1=s[k],s2=1ll*s[k+(i>>1)]*wn[num[i]][k-j]%mod,s[k]=MD(s1+s2),s[k+(i>>1)]=MD2(s1-s2);
	}
	else
	{
		for (int i=2;i<=limit;i<<=1)
			for (int j=0;j+i-1<limit;j+=i)
				for (int k=j;k<j+(i>>1);++k)
					s1=s[k],s2=1ll*s[k+(i>>1)]*wn2[num[i]][k-j]%mod,s[k]=MD(s1+s2),s[k+(i>>1)]=MD2(s1-s2);
		s1=fast_pow(limit,mod-2);
		for (int i=0;i<=limit;++i) s[i]=1ll*s[i]*s1%mod;
	}
	return;
}
vector<int>operator * (vector<int>a,vector<int>b)
{
	vector<int>c(a.size()+b.size()-1);
	int limit=1;
	while (limit<=c.size()) limit<<=1;
	for (int i=0;i<=limit;++i) A[i]=B[i]=0;
	for (int i=0;i<a.size();++i) A[i]=a[i];
	for (int i=0;i<b.size();++i) B[i]=b[i];
	NTT(limit,A,1),NTT(limit,B,1);
	for (int i=0;i<=limit;++i) A[i]=1ll*A[i]*B[i]%mod;
	NTT(limit,A,-1);
	for (int i=0;i<c.size();++i) c[i]=A[i];
	return c;
}
vector<int>revs(vector<int>a)
{
	reverse(a.begin(),a.end());
	return a;
}
vector<int>calc(vector<int>a,int b)
{
	vector<int>c;
	for (int i=(int)(a.size()>>1)-b;i<=(int)(a.size()>>1)+b;++i) c.push_back(a[i]);
	return c;
}
struct seg
{
	struct node
	{
		int l,r;
		vector<int>data;
	};
	node tree[(N<<2)+1];
	void push_up(int k)
	{
		tree[k].data=tree[k<<1].data*tree[k<<1|1].data;
		return;
	}
	void build(int k,int l,int r)
	{
		tree[k].l=l,tree[k].r=r;
		if (l==r)
		{
			tree[k].data={sx[1],sx[2],sx[3],sx[4],sx[5]};
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
		return;
	}
	void solve(int k,vector<int>res)
	{
		while (res.size()>((tree[k].r-tree[k].l+1)<<2)+1) res=calc(res,(tree[k].r-tree[k].l+1)<<1);
		if (tree[k].l==tree[k].r)
		{
			for (int i=0;i<=4;++i) Adder(F[tree[k].l],1ll*res[i]*sx[i+1]%mod);
			return;
		}
		solve(k<<1,res),solve(k<<1|1,res*revs(tree[k<<1].data));
		return;
	}
};
seg T;
void get(int x)
{
	for (int i=0;i<=m;++i) F[i]=0;
	if (x<-(m<<1)||x>(m<<1)) return;
	vector<int>p((m<<2)+1);
	p[x+(m<<1)]=1,T.solve(1,p);
	return;
}
void solve(int l,int r)
{
	if (l==r) return;
	int mid=(l+r)>>1;
	vector<int>a(mid-l+1);
	vector<int>b(mid-l+1);
	vector<int>c(r-l+1);
	vector<int>d(r-l+1);
	vector<int>e(r-l+1);
	vector<int>st1;
	vector<int>st2;
	vector<int>st3;
	vector<int>st4;
	vector<int>st5;
	solve(l,mid);
	for (int i=l;i<=mid;++i) a[i-l]=dp[i][0],b[i-l]=dp[i][1];
	for (int i=1;i<=r-l;++i) c[i]=delta[i-1],d[i]=delta2[i-1],e[i]=delta3[i-1];
	st1=a*c,st2=a*d,st3=b*c,st4=b*d,st5=a*e;
	for (int i=mid+1;i<=r;++i)
	{
		Adder2(dp[i][0],-1ll*st1[i-l]*sx[2]%mod);
		Adder2(dp[i][0],-1ll*st2[i-l]*sx[1]%mod);
		Adder2(dp[i][0],-1ll*st3[i-l]*sx[1]%mod);
		Adder2(dp[i][1],-1ll*st2[i-l]*sx[2]%mod);
		Adder2(dp[i][1],-1ll*st5[i-l]*sx[1]%mod);
		Adder2(dp[i][1],-1ll*st4[i-l]*sx[1]%mod);
	}
	solve(mid+1,r);
	return;
}
int main()
{
	int rst=0;
	for (int i=2,w;i<=M;i<<=1)
	{
		num[i]=++length,w=fast_pow(g,(mod-1)/i);
		for (int j=0,res=1;j<(i>>1);++j,res=1ll*res*w%mod) wn[num[i]][j]=res;
		w=fast_pow(g,(mod-1)/i*(i-1));
		for (int j=0,res=1;j<(i>>1);++j,res=1ll*res*w%mod) wn2[num[i]][j]=res;
	}
	n=read(),m=read();
	if (!m)
	{
		puts("1");
		return 0;
	}
	for (int i=1;i<=5;++i) sx[i]=read(),Adder(rst,sx[i]);
	for (int i=1;i<=5;++i) sx[i]=1ll*sx[i]*fast_pow(rst,mod-2)%mod;
	T.build(1,1,m);
	get(1);
	for (int i=1;i<=m;++i) delta[i]=F[i];
	get(2);
	for (int i=1;i<=m;++i) delta2[i]=F[i];
	get(3);
	for (int i=1;i<=m;++i) delta3[i]=F[i];
	get(-n),delta4[0]=(n==0);
	for (int i=1;i<=m;++i) delta4[i]=F[i];
	get(-n+1),delta5[0]=(n==1);
	for (int i=1;i<=m;++i) delta5[i]=F[i];
	for (int i=0;i<=m;++i) dp[i][0]=delta4[i],dp[i][1]=delta5[i];
	solve(0,m);
	for (int i=0;i<=m-1;++i)
	{
		Adder2(ans,-1ll*dp[i][0]*sx[2]%mod);
		Adder2(ans,-1ll*dp[i][0]*sx[1]%mod);
		Adder2(ans,-1ll*dp[i][1]*sx[1]%mod);
	}
	printf("%d\n",ans);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 112664kb

input:

1 1
1 1 1 1 1

output:

399297742

result:

ok 1 number(s): "399297742"

Test #2:

score: 0
Accepted
time: 6797ms
memory: 164012kb

input:

100000 100000
1234 4567 7890 4321 54321

output:

348074135

result:

ok 1 number(s): "348074135"

Test #3:

score: 0
Accepted
time: 6763ms
memory: 170748kb

input:

100000 100000
1 2 3 4 5

output:

639188342

result:

ok 1 number(s): "639188342"

Test #4:

score: 0
Accepted
time: 6793ms
memory: 164300kb

input:

100000 100000
5 4 3 2 1

output:

211669278

result:

ok 1 number(s): "211669278"

Test #5:

score: 0
Accepted
time: 15ms
memory: 113440kb

input:

0 0
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 3024ms
memory: 151160kb

input:

1 50000
1 1 1 1 1

output:

548880636

result:

ok 1 number(s): "548880636"

Test #7:

score: 0
Accepted
time: 11ms
memory: 114256kb

input:

50000 1
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 6743ms
memory: 165324kb

input:

100000 100000
234 666 7655 12234 0

output:

45268602

result:

ok 1 number(s): "45268602"

Test #9:

score: 0
Accepted
time: 6873ms
memory: 165068kb

input:

99999 99999
12345 54332 12345 65432 34444

output:

360543661

result:

ok 1 number(s): "360543661"

Test #10:

score: 0
Accepted
time: 6787ms
memory: 169336kb

input:

99998 99998
1 1 1 1 1

output:

602326230

result:

ok 1 number(s): "602326230"

Test #11:

score: 0
Accepted
time: 6823ms
memory: 164156kb

input:

99998 99997
1 1 1 1 1

output:

159752985

result:

ok 1 number(s): "159752985"

Test #12:

score: 0
Accepted
time: 6744ms
memory: 177804kb

input:

99997 100000
1 2 3 4 5

output:

139603712

result:

ok 1 number(s): "139603712"

Test #13:

score: 0
Accepted
time: 6721ms
memory: 170380kb

input:

100000 99997
1 2 2 1 3232323

output:

363030953

result:

ok 1 number(s): "363030953"

Test #14:

score: 0
Accepted
time: 8ms
memory: 106252kb

input:

0 0
0 0 1 0 0

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 338ms
memory: 117732kb

input:

10000 10000
91095828 93770094 5303328 491263 50290308

output:

135900098

result:

ok 1 number(s): "135900098"

Test #16:

score: 0
Accepted
time: 345ms
memory: 137344kb

input:

9226 9995
62366139 253808 1929312 491263 4375669

output:

812662634

result:

ok 1 number(s): "812662634"

Test #17:

score: 0
Accepted
time: 343ms
memory: 117984kb

input:

18641 10000
1061 4359 1330 13764 16043

output:

112339046

result:

ok 1 number(s): "112339046"

Extra Test:

score: 0
Extra Test Passed