QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#75615 | #4922. 生活在对角线下 | 4182_543_731 | 0 | 644ms | 49952kb | C++ | 5.6kb | 2023-02-05 22:23:41 | 2023-02-05 22:23:43 |
Judging History
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%