QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#75573 | #4903. 细菌 | 4182_543_731 | 100 ✓ | 1413ms | 21080kb | C++ | 2.7kb | 2023-02-05 20:40:54 | 2023-02-05 20:40:56 |
Judging History
answer
#include<cstdio>
#include<vector>
using namespace std;
#define N 263001
#define mod 998244353
int n,l1,l2,l3,s1,s2,s3;
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],ifr[N],gr[2][N*2],rev[N*2];
void init(int l=18)
{
fr[0]=1;for(int i=1;i<=1<<l;i++)fr[i]=1ll*i*fr[i-1]%mod;
ifr[1<<l]=pw(fr[1<<l],mod-2);for(int i=1<<l;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>>1;i++)gr[t][s+i]=vl,vl=1ll*vl*tp%mod;
}
}
int f[N],g[N],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++)
{
int v1=ntt[i+j],v2=1ll*ntt[i+j+(l>>1)]*gr[t][j+l]%mod;
ntt[i+j]=(v1+v2)%mod;ntt[i+j+(l>>1)]=(v1+mod-v2)%mod;
}
int tp=t?1:pw(s,mod-2);
for(int i=0;i<s;i++)a[i]=1ll*ntt[i]*tp%mod;
}
int v1[N],v2[N],v3[N];
int as[N];
void solve(int n,int lb,vector<int> si)
{
if(n<=64)
{
for(int i=0;i<=n;i++)
{
as[i+lb]=si[n];
for(int i=n*2;i>=1;i--)si[i]=(si[i]+si[i-1])%mod;
for(int i=0;i<n*2;i++)si[i]=(si[i]+si[i+1])%mod;
}
return;
}
int mid=n>>1,l=1;
while(l<=n*3)l<<=1;
for(int i=0;i<l;i++)f[i]=g[i]=0;
for(int i=0;i<=mid*2;i++)g[i]=1ll*fr[mid*2]*ifr[i]%mod*ifr[mid*2-i]%mod;
for(int i=0;i<=n*2;i++)f[i]=si[i];
dft(l,f,1);dft(l,g,1);for(int i=0;i<l;i++)f[i]=1ll*f[i]*g[i]%mod;dft(l,f,0);
vector<int> s1,s2;
for(int i=0;i<=(n-mid)*2;i++)s1.push_back(f[mid*2+i]);
for(int i=0;i<=(mid-1)*2;i++)s2.push_back(si[n-(mid-1)+i]);
solve(mid-1,lb,s2);
solve(n-mid,lb+mid,s1);
}
void calc(int n,int m,int s,int *v)
{
vector<int> s1,s2;
int tp=n/2;
for(int i=0;i<=tp*2;i++)
{
int rt=s+tp*2-i*2;
rt=(rt%(2*m+2)+2*m+2)%(2*m+2);
if(rt%(m+1)==0)s1.push_back(0);
else if(rt<m+1)s1.push_back(1);
else s1.push_back(mod-1);
int rv=0;
rt=(rt+2*m+1)%(2*m+2);
if(rt%(m+1)!=0)rv+=rt<m+1?1:-1;
rt=(rt+2)%(2*m+2);
if(rt%(m+1)!=0)rv+=rt<m+1?1:-1;
s2.push_back((mod+rv)%mod);
}
solve(tp,0,s1);for(int i=0;i<=tp;i++)v[i*2]=as[i];
solve(tp,0,s2);for(int i=0;i<=tp;i++)v[i*2+1]=as[i];
}
int main()
{
init();
scanf("%d%d%d%d%d%d%d",&n,&l1,&l2,&l3,&s1,&s2,&s3);
calc(n,l1,s1,v1);
calc(n,l2,s2,v2);calc(n,l3,s3,v3);
for(int i=0;i<=n;i++)v1[i]=1ll*ifr[i]*v1[i]%mod,v2[i]=1ll*ifr[i]*v2[i]%mod,v3[i]=1ll*ifr[i]*v3[i]%mod;
int l=1;while(l<=n*2)l<<=1;
dft(l,v1,1);dft(l,v2,1);
for(int i=0;i<l;i++)v1[i]=1ll*v1[i]*v2[i]%mod;dft(l,v1,0);
int rs=0;
for(int i=0;i<=n;i++)rs=(rs+1ll*v3[i]*v1[n-i])%mod;
printf("%d\n",1ll*rs*fr[n]%mod);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 10ms
memory: 15360kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 9ms
memory: 15308kb
input:
50 49 44 48 49 15 25
output:
544847893
result:
ok 1 number(s): "544847893"
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #3:
score: 10
Accepted
time: 32ms
memory: 15584kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 27ms
memory: 15536kb
input:
5000 4994 4997 4994 4399 1826 1332
output:
65414465
result:
ok 1 number(s): "65414465"
Subtask #3:
score: 15
Accepted
Test #5:
score: 15
Accepted
time: 1370ms
memory: 20120kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 1376ms
memory: 20168kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 1361ms
memory: 19852kb
input:
120000 119999 1 1 19896 1 1
output:
68846585
result:
ok 1 number(s): "68846585"
Subtask #4:
score: 10
Accepted
Test #8:
score: 10
Accepted
time: 1358ms
memory: 19784kb
input:
119000 119991 119991 1 23819 52139 1
output:
944500934
result:
ok 1 number(s): "944500934"
Subtask #5:
score: 15
Accepted
Dependency #4:
100%
Accepted
Test #9:
score: 15
Accepted
time: 1361ms
memory: 21036kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 0
Accepted
time: 1349ms
memory: 20048kb
input:
120000 13997 13997 1 9768 6131 1
output:
151873213
result:
ok 1 number(s): "151873213"
Subtask #6:
score: 35
Accepted
Dependency #3:
100%
Accepted
Dependency #5:
100%
Accepted
Test #11:
score: 35
Accepted
time: 1353ms
memory: 20936kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 0
Accepted
time: 1357ms
memory: 20112kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: 0
Accepted
time: 1351ms
memory: 20456kb
input:
120000 491 495 1 430 25 1
output:
272929924
result:
ok 1 number(s): "272929924"
Test #14:
score: 0
Accepted
time: 1351ms
memory: 19844kb
input:
120000 590 593 1 418 459 1
output:
446962505
result:
ok 1 number(s): "446962505"
Test #15:
score: 0
Accepted
time: 1353ms
memory: 20296kb
input:
120000 697 690 1 166 450 1
output:
216092107
result:
ok 1 number(s): "216092107"
Test #16:
score: 0
Accepted
time: 1382ms
memory: 20124kb
input:
120000 793 799 1 416 61 1
output:
661260042
result:
ok 1 number(s): "661260042"
Test #17:
score: 0
Accepted
time: 1382ms
memory: 19816kb
input:
120000 1000 1000 1 613 547 1
output:
429669083
result:
ok 1 number(s): "429669083"
Test #18:
score: 0
Accepted
time: 1368ms
memory: 20268kb
input:
120000 1993 1995 1 493 565 1
output:
609392900
result:
ok 1 number(s): "609392900"
Test #19:
score: 0
Accepted
time: 1413ms
memory: 20284kb
input:
120000 4995 4998 1 3166 3765 1
output:
394497547
result:
ok 1 number(s): "394497547"
Test #20:
score: 0
Accepted
time: 1409ms
memory: 20348kb
input:
120000 9994 9991 1 6099 691 1
output:
795651799
result:
ok 1 number(s): "795651799"
Test #21:
score: 0
Accepted
time: 1395ms
memory: 21080kb
input:
120000 49990 49990 1 41933 2862 1
output:
360787513
result:
ok 1 number(s): "360787513"
Test #22:
score: 0
Accepted
time: 1401ms
memory: 20016kb
input:
120000 119996 119994 1 58014 49559 1
output:
682979057
result:
ok 1 number(s): "682979057"
Subtask #7:
score: 10
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #23:
score: 10
Accepted
time: 1390ms
memory: 20164kb
input:
120000 296 300 297 89 130 280
output:
702788425
result:
ok 1 number(s): "702788425"
Test #24:
score: 0
Accepted
time: 1411ms
memory: 19700kb
input:
120000 392 397 391 222 280 10
output:
322470184
result:
ok 1 number(s): "322470184"
Test #25:
score: 0
Accepted
time: 1384ms
memory: 20044kb
input:
120000 499 498 500 263 315 367
output:
449848666
result:
ok 1 number(s): "449848666"
Test #26:
score: 0
Accepted
time: 1390ms
memory: 21028kb
input:
120000 598 591 594 497 474 400
output:
35486519
result:
ok 1 number(s): "35486519"
Test #27:
score: 0
Accepted
time: 1389ms
memory: 21072kb
input:
120000 694 692 695 625 173 477
output:
785203749
result:
ok 1 number(s): "785203749"
Test #28:
score: 0
Accepted
time: 1386ms
memory: 20212kb
input:
120000 794 796 800 395 465 507
output:
897269426
result:
ok 1 number(s): "897269426"
Test #29:
score: 0
Accepted
time: 1387ms
memory: 19928kb
input:
120000 993 998 991 196 712 911
output:
464727191
result:
ok 1 number(s): "464727191"
Test #30:
score: 0
Accepted
time: 1345ms
memory: 20756kb
input:
120000 1991 2000 1994 1937 1362 1494
output:
473701811
result:
ok 1 number(s): "473701811"
Test #31:
score: 0
Accepted
time: 1373ms
memory: 20272kb
input:
120000 4994 4990 4990 646 1214 2276
output:
763540821
result:
ok 1 number(s): "763540821"
Test #32:
score: 0
Accepted
time: 1347ms
memory: 19960kb
input:
120000 9994 9992 9991 6588 9538 2632
output:
804858722
result:
ok 1 number(s): "804858722"
Test #33:
score: 0
Accepted
time: 1390ms
memory: 20304kb
input:
120000 49997 49997 49993 46278 44140 26931
output:
139550295
result:
ok 1 number(s): "139550295"
Test #34:
score: 0
Accepted
time: 1356ms
memory: 20096kb
input:
120000 119997 120000 120000 24867 116477 35338
output:
946147605
result:
ok 1 number(s): "946147605"