QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75615#4922. 生活在对角线下4182_543_7310 644ms49952kbC++5.6kb2023-02-05 22:23:412023-02-05 22:23:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 22:23:43]
  • 评测
  • 测评结果:0
  • 用时:644ms
  • 内存:49952kb
  • [2023-02-05 22:23:41]
  • 提交

answer

#include<cstdio>
using namespace std;
#define N 263001
#define M 11
#define mod 998244353
int pw(int a,int p){int as=1;while(p){if(p&1)as=1ll*as*a%mod;a=1ll*a*a%mod;p>>=1;}return as;}
int fr[N*2],ifr[N*2],gr[2][N*2],rev[N*2];
void init(int l=18)
{
	fr[0]=1;for(int i=1;i<=1<<l+1;i++)fr[i]=1ll*i*fr[i-1]%mod;
	ifr[1<<l+1]=pw(fr[1<<l+1],mod-2);for(int i=1<<l+1;i>=1;i--)ifr[i-1]=1ll*i*ifr[i]%mod;
	for(int s=2;s<=1<<l;s<<=1)for(int i=1;i<s;i++)rev[i+s]=(rev[(i>>1)+s]>>1)+((i&1)*(s>>1));
	for(int t=0;t<2;t++)
	for(int s=2;s<=1<<l;s<<=1)
	{
		int tp=pw(3,(mod-1)/s);
		if(!t)tp=pw(tp,mod-2);
		int vl=1;
		for(int i=0;i<s;i++)gr[t][s+i]=vl,vl=1ll*vl*tp%mod;
	}
}
int f[N],g[N];
long long ntt[N];
void dft(int s,int *a,int t)
{
	for(int i=0;i<s;i++)ntt[rev[i+s]]=a[i];
	for(int l=2;l<=s;l<<=1)
	for(int i=0;i<s;i+=l)
	for(int j=0;j<l>>1;j++)
	{
		long long v1=ntt[i+j],v2=ntt[i+j+(l>>1)]*gr[t][j+l]%mod;
		ntt[i+j]=v1+v2;ntt[i+j+(l>>1)]=v1+mod-v2;
	}
	int tp=t?1:pw(s,mod-2);
	for(int i=0;i<s;i++)a[i]=1ll*ntt[i]*tp%mod;
}
void polyinv(int n,int *s,int *t)
{
	if(n==1){t[0]=pw(s[0],mod-2);return;}
	polyinv((n+1)>>1,s,t);
	int l=1;while(l<=n*2+4)l<<=1;
	for(int i=0;i<l;i++)f[i]=g[i]=0;
	for(int i=0;i<n;i++)f[i]=s[i],g[i]=t[i];
	dft(l,f,1);dft(l,g,1);for(int i=0;i<l;i++)f[i]=1ll*g[i]*(2+mod-1ll*f[i]*g[i]%mod)%mod;
	dft(l,f,0);
	for(int i=0;i<n;i++)t[i]=f[i];
}

int cl[N],ls[M][N],vl[M][N],fi[M][N],tp[N],rs[N],iri[N],ri[N],c[M][M];
void solve_cl(int n,int p,int q)
{
	for(int i=0;i<=10;i++)c[i][0]=c[i][i]=1;
	for(int i=2;i<=10;i++)for(int j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	int l=1;while(l<=n*2+3)l<<=1;
	cl[0]=1;for(int i=1;i<=n;i++)cl[i]=1ll*cl[i-1]*(4*i-2)%mod*pw(i+1,mod-2)%mod;
	for(int i=0;i<=n;i++)rs[i]=cl[i];
	dft(l,rs,1);
	for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
	{
		//ls*rs
		for(int i=0;i<=n;i++)ls[a*(q+1)+b][i]=1ll*cl[i]*pw(i+1,a)%mod*pw(i,b)%mod;
		dft(l,ls[a*(q+1)+b],1);
		for(int i=0;i<l;i++)ls[a*(q+1)+b][i]=1ll*ls[a*(q+1)+b][i]*rs[i]%mod;
		dft(l,ls[a*(q+1)+b],0);
		for(int i=n+1;i<l;i++)ls[a*(q+1)+b][i]=0;
		dft(l,ls[a*(q+1)+b],1);
		//fi
		for(int i=0;i<=n;i++)fi[a*(q+1)+b][i]=1ll*cl[i]*pw(i,a)%mod*pw(i+1,b)%mod;
		dft(l,fi[a*(q+1)+b],1);
	}
	// / 1-ls_0*x
	dft(l,ls[0],0);
	ri[0]=1;for(int i=1;i<=n;i++)ri[i]=mod-ls[0][i-1];
	polyinv(n+1,ri,iri);
	dft(l,iri,1);
	dft(l,ls[0],1);
	for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
	{
		for(int i=0;i<l;i++)tp[i]=0;
		//vl_(a,b)=x*(vl_(a,b)+f_i)*ls+c
		if(a+b==0)
		{
			for(int i=0;i<=n;i++)tp[i]=cl[i];
			dft(l,tp,1);
		}
		for(int a1=0;a1<=a;a1++)for(int b1=0;b1<=b;b1++)
		for(int i=0;i<l;i++)tp[i]=(tp[i]+1ll*c[a][a1]*c[b][b1]*gr[1][l+i]%mod*
		(vl[a1*(q+1)+b1][i]+fi[a1*(q+1)+b1][i])%mod*ls[(a-a1)*(q+1)+(b-b1)][i])%mod;
		dft(l,tp,0);
		for(int i=n+1;i<l;i++)tp[i]=0;
		dft(l,tp,1);
		for(int i=0;i<l;i++)tp[i]=1ll*tp[i]*iri[i]%mod;
		dft(l,tp,0);
		for(int i=0;i<=n;i++)vl[a*(q+1)+b][i]=tp[i];
		dft(l,vl[a*(q+1)+b],1);
	}
}
int ls2[M][N],t1[N];
void solve_c2(int n,int p,int q,int d)
{
	int l=1;while(l<=n*2+3)l<<=1;
	for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
	{
		for(int i=0;i<=n;i++)ls2[a*(q+1)+b][i]=1ll*(i?1ll*fr[i*2-1]*ifr[i]%mod*ifr[i-1]%mod:1)*pw(i,a+b)%mod;
		dft(l,ls2[a*(q+1)+b],1);
	}
	for(int a=p;a>=0;a--)for(int b=q;b>=0;b--)
	{
		for(int i=0;i<l;i++)vl[a*(q+1)+b][i]=1ll*vl[a*(q+1)+b][i]*ls2[0][i]%mod;
		for(int a1=0;a1<=a;a1++)for(int b1=0;b1<=b;b1++)if(a1+b1<a+b)
		for(int i=0;i<l;i++)vl[a*(q+1)+b][i]=(vl[a*(q+1)+b][i]+1ll*c[a][a1]*c[b][b1]*
		vl[a1*(q+1)+b1][i]%mod*ls2[(a-a1)*(q+1)+(b-b1)][i]%mod)%mod;
		dft(l,vl[a*(q+1)+b],0);
		for(int i=n+1;i<l;i++)vl[a*(q+1)+b][i]=0;
	}
	for(int i=0;i<=n;i++)t1[i]=i?1ll*fr[2*i+d-1]*ifr[i+d-1]%mod*ifr[i]%mod:1;
	dft(l,t1,1);
	for(int a=p;a>=0;a--)for(int b=q;b>=0;b--)
	{
		dft(l,vl[a*(q+1)+b],1);
		for(int i=0;i<l;i++)vl[a*(q+1)+b][i]=1ll*vl[a*(q+1)+b][i]*t1[i]%mod;
		dft(l,vl[a*(q+1)+b],0);
	}
}
int al[M][N],s1[M][M],t2[N];
void solve_a1(int n,int p,int q,int c)
{
	int l=1;while(l<=n*2+3)l<<=1;
	for(int i=0;i<=n;i++)t2[i]=1ll*fr[2*i+c]*ifr[i+c]%mod*ifr[i]%mod;
	dft(l,t2,1);
	for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
	{
		for(int i=0;i<=n;i++)al[a*(q+1)+b][i]=1ll*fr[i*2]*ifr[i]%mod*ifr[i]%mod*pw(i,a+b)%mod;
		dft(l,al[a*(q+1)+b],1);
		for(int i=0;i<l;i++)al[a*(q+1)+b][i]=1ll*al[a*(q+1)+b][i]*t2[i]%mod;
		dft(l,al[a*(q+1)+b],0);
	}
	s1[0][0]=1;
	for(int i=1;i<=10;i++)for(int j=1;j<=i;j++)s1[i][j]=1ll*j*(s1[i-1][j]+s1[i-1][j-1])%mod;
	for(int i=0;i<=n;i++)
	for(int a=0;a<=p&&a<=i;a++)for(int b=0;b<=q&&b<=i+c;b++)
	{
		int si=1ll*ifr[a]%mod*ifr[b]%mod*ifr[i-a]%mod*ifr[i+c-b]%mod*fr[i*2+c]%mod;
		if(a<i)si=(si+1ll*ifr[a]%mod*ifr[b]%mod*ifr[i-a-1]%mod*ifr[i+c-b]%mod*fr[i*2+c]%mod*ifr[a+b+1]%mod*fr[a+b])%mod;
		if(b<i+c)si=(si+1ll*ifr[a]%mod*ifr[b]%mod*ifr[i-a]%mod*ifr[i+c-b-1]%mod*fr[i*2+c]%mod*ifr[a+b+1]%mod*fr[a+b])%mod;
		for(int a2=a;a2<=p;a2++)for(int b2=b;b2<=q;b2++)
		al[a2*(q+1)+b2][i]=(al[a2*(q+1)+b2][i]+1ll*s1[a2][a]*s1[b2][b]*si)%mod;
	}
}
int T,d,p,q,n,fg,v[M][M],m;
int main()
{
	scanf("%d%d%d%d%d",&T,&d,&p,&q,&n);
	init();
	if(d<0)p^=q^=p^=q,d*=-1,fg=1;
	solve_cl(n,p,q);
	solve_c2(n,p,q,d);
	if(fg)solve_a1(n,p,q,d);
	while(T--)
	if(fg)
	{
		int as=0;
		scanf("%*d%d",&m);
		for(int i=0;i<=q;i++)for(int j=0;j<=p;j++)scanf("%d",&v[j][i]);
		for(int i=0;i<=p;i++)for(int j=0;j<=q;j++)as=(as+1ll*v[i][j]*(al[i*(q+1)+j][m]+mod-vl[i*(q+1)+j][m]))%mod;
		printf("%d\n",as);
	}
	else
	{
		int as=0;
		scanf("%d%*d",&m);
		for(int i=0;i<=p;i++)for(int j=0;j<=q;j++)scanf("%d",&v[i][j]);
		for(int i=0;i<=p;i++)for(int j=0;j<=q;j++)as=(as+1ll*v[i][j]*vl[i*(q+1)+j][m])%mod;
		printf("%d\n",as);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 17ms
memory: 28492kb

input:

1 -10 1 2 1000
825 815
107973512 400177523 812303207
164088430 603506669 337780072

output:

252142100

result:

wrong answer 1st numbers differ - expected: '360076089', found: '252142100'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 161ms
memory: 33196kb

input:

1 4683 0 0 95317
86560 91243
412303217

output:

178751410

result:

wrong answer 1st numbers differ - expected: '952052072', found: '178751410'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Wrong Answer

Test #41:

score: 0
Wrong Answer
time: 644ms
memory: 49952kb

input:

100000 0 2 1 100000
48964 48964
666670967 90494987
74847122 615108201
29533064 582540229
14418 14418
391779909 223696706
701170191 885097597
551643398 25626747
81584 81584
951326734 520293397
13860946 896899117
821166399 282263457
76849 76849
598606953 879771697
930252135 671750715
673503431 3060699...

output:

62984778
225376805
570666351
-195001571
941851080
255992837
-601602059
89249308
-762846305
211097834
-288139553
124329451
-417084731
797694549
450965643
-800539541
-306445578
198033167
-206733147
-873640294
346287614
650535853
-590928182
324564525
145010687
-147146640
845311782
-557114767
-787310674...

result:

wrong answer 1st numbers differ - expected: '513261452', found: '62984778'

Subtask #7:

score: 0
Skipped

Dependency #1:

0%