QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#75616#4922. 生活在对角线下4182_543_731Compile Error//C++5.7kb2023-02-05 22:25:002023-02-05 22:25:02

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:25:02]
  • 评测
查看
  • [2023-02-05 22:25:00]
  • 提交

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=(unsigned long long)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]=(unsigned long longntt[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);
	}
}
源文件, 语言: C++

詳細信息 

answer.code: In function ‘void dft(int, int*, int)’:
answer.code:35:35: error: expected primary-expression before ‘unsigned’
   35 |         for(int i=0;i<s;i++)a[i]=(unsigned long longntt[i]*tp%mod;
      |                                   ^~~~~~~~
answer.code:35:35: error: expected ‘)’ before ‘unsigned’
   35 |         for(int i=0;i<s;i++)a[i]=(unsigned long longntt[i]*tp%mod;
      |                                  ~^~~~~~~~
      |                                   )
answer.code: In function ‘int main()’:
answer.code:153:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  153 |         scanf("%d%d%d%d%d",&T,&d,&p,&q,&n);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:163:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  163 |                 scanf("%*d%d",&m);
      |                 ~~~~~^~~~~~~~~~~~
answer.code:164:64: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  164 |                 for(int i=0;i<=q;i++)for(int j=0;j<=p;j++)scanf("%d",&v[j][i]);
      |                                                           ~~~~~^~~~~~~~~~~~~~~
answer.code:171:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  171 |                 scanf("%d%*d",&m);
      |                 ~~~~~^~~~~~~~~~~~
answer.code:172:64: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  172 |                 for(int i=0;i<=p;i++)for(int j=0;j<=q;j++)scanf("%d",&v[i][j]);
      |                                                           ~~~~~^~~~~~~~~~~~~~~
English 繁體中文 简体中文

伺服器時間: 2024-12-02 17:03:58 | 開源專案