QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87580 | #4903. 细菌 | H_zwei | 100 ✓ | 801ms | 33364kb | C++14 | 7.9kb | 2023-03-13 19:47:59 | 2023-03-13 19:48:01 |
Judging History
answer
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC target("avx,avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("Ofast,fast-math")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#include<iostream>
//#include<string>
//#include<cmath>
//#include<cstdio>
//#include<cctype>
//#include<cstring>
//#include<iomanip>
//#include<cstdlib>
//#include<ctime>
//#include<set>
//#include<map>
//#include<utility>
//#include<queue>
//#include<vector>
//#include<stack>
//#include<sstream>
//#include<algorithm>
using namespace std;
/*=====================================================================*/
#define ll long long
#define int ll
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pdd pair<double,double>
#define ull unsigned long long
#define pb push_back
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(s) (s).begin(),(s).end()
#define repd(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define forr(i,a,b,c) for(int i=(int)(a);i<=(int)(b);i+=(int)(c))
#define forn(i,p,n) for(int i=(int)(p);i<=(int)(n);++i)
#define ford(i,p,n) for(int i=(int)(n);i>=(int)(p);--i)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();++i)
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define Endl(x) cout<<x<<endl;
#define Blank(x) cout<<x<<" ";
#define modcg(x) if(x>=mod)x-=mod;
#define modcl(x) if(x<0)x+=mod;
#define lowbit(x) x&(-x)
/*=====================================================================*/
string int_to_string(ll n)
{
string s="";
while(n)
{
ll now=n%10;
s+=now+'0';
n/=10;
}
reverse(s.begin(),s.end());
return s;
}
ll string_to_int(string s)
{
ll n=0;
rep(i,s.size())
{
n*=10;
n+=s[i]-'0';
}
return n;
}
mt19937 GeN(chrono::system_clock::now().time_since_epoch().count());
int Rand(int l,int r)
{
uniform_int_distribution<>RAND1(l,r);
return RAND1(GeN);
}
/*======================================================================*/
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
const int month[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};
//think twice,code once
//think once,debug forever
const int MAXN=480020;
const int mod=998244353,gen=3,igen=332748118;
int quickpower(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
{
res*=a;
res%=mod;
}
a*=a;
a%=mod;
b>>=1;
}
return res;
}
int inv(int x)
{
return quickpower(x,mod-2);
}
struct Poly
{
int r[MAXN];
int limit,l,invl;
void init(int n)
{
l=0;
limit=1;
while(limit<n)
{
limit<<=1;
l++;
}
invl=::inv(limit);
rep(i,limit)
{
r[i]=(r[i>>1]>>1ll)|((i&1ll)<<(l-1));
}
}
void NTT(vi &a,bool type)
{
a.resize(limit);
rep(i,limit)
{
if(i<r[i])
{
swap(a[i],a[r[i]]);
}
}
for(int i=2;;i<<=1)
{
if(i>limit)
{
break;
}
int Gen=quickpower(((type==1)?gen:igen),(mod-1)/i);
forr(j,0,limit-1,i)
{
int w=1;
forn(k,j,(i>>1)+j-1)
{
int cur=w*a[k+(i>>1)]%mod;
a[k+(i>>1)]=((a[k]-cur)%mod+mod)%mod;
a[k]=(a[k]+cur)%mod;
w*=Gen;
w%=mod;
}
}
}
}
vi mul(vi f,vi g)
{
int n=f.size();
int m=g.size();
init(n+m);
NTT(f,1);
NTT(g,1);
rep(i,limit)
{
f[i]=f[i]*g[i]%mod*invl%mod;
}
NTT(f,0);
f.resize(n+m);
return f;
}
vi inv(vi f)
{
if(f.size()==1)
{
f[0]=::inv(f[0]);
return f;
}
int all=f.size();
vi nf=f;
nf.resize((all+1)/2);
nf=inv(nf);
vi nf1=nf;
nf1=mul(nf1,f);
nf1.resize(all);
rep(i,nf1.size())
{
nf1[i]=-nf1[i];
modcl(nf1[i]);
}
nf1[0]+=2;
modcg(nf1[0]);
f=mul(nf,nf1);
f.resize(all);
return f;
}
}P;
struct combination
{
int F[MAXN],invF[MAXN];
int P[MAXN];
void init(int n)
{
F[0]=1;
P[0]=1;
forn(i,1,n)
{
F[i]=(F[i-1]*i)%mod;
P[i]=P[i-1]+P[i-1];
modcg(P[i]);
}
invF[n]=inv(F[n]);
ford(i,0,n-1)
{
invF[i]=(invF[i+1]*(i+1))%mod;
}
}
int C(int n,int m)
{
if(n<0||m<0||n<m)
{
return 0;
}
return ((F[n]*invF[m])%mod*invF[n-m])%mod;
}
int A(int n,int m)
{
if(n<0||m<0||n<m)
{
return 0;
}
return F[n]*invF[n-m]%mod;
}
}C;
int n[3];
int x[3];
int d;
vi ans[3];
void doit(int id)
{
vi S,A;
S.resize(d+1);
A.resize(d+1);
int a=x[id],b=n[id]+1-x[id];
forn(i,1,d)
{
if((i-a>=0)&&(!((i-a)&1)))
{
S[i]+=C.C(i,(i-a)>>1);
modcg(S[i]);
}
if((i-b>=0)&&(!((i-b)&1)))
{
S[i]+=C.C(i,(i-b)>>1);
modcg(S[i]);
}
if(!(i&1))
{
A[i]+=C.C(i,i>>1);
modcg(A[i]);
}
if((i-n[id]-1>=0)&&(!((i-n[id]-1)&1)))
{
A[i]+=C.C(i,(i-n[id]-1)>>1);
modcg(A[i]);
}
}
A[0]=1;
// S[0]=0;
// for(int u:A)
// {
// cout<<u<<" ";
// }
// cout<<endl;
// for(int u:S)
// {
// cout<<u<<" ";
// }
// cout<<endl;
A=P.inv(A);
ans[id]=P.mul(A,S);
ans[id].resize(d+1);
// for(int u:ans[id])
// {
// cout<<u<<" ";
// }
// cout<<endl;
ans[id][0]=C.P[0];
forn(i,1,d)
{
ans[id][i]=-ans[id][i];
modcl(ans[id][i]);
ans[id][i]+=ans[id][i-1];
modcg(ans[id][i]);
ans[id][i]+=ans[id][i-1];
modcg(ans[id][i]);
}
forn(i,0,d)
{
ans[id][i]*=C.invF[i];
ans[id][i]%=mod;
// cout<<ans[id][i]<<" ";
}
// cout<<endl;
}
void solve()
{
cin>>d;
rep(i,3)
{
cin>>n[i];
}
rep(i,3)
{
cin>>x[i];
}
C.init(d);
rep(i,3)
{
doit(i);
}
// rep(i,3)
// {
// for(int u:ans[i])
// {
// cout<<u<<" ";
// }
// cout<<endl;
// }
ans[0]=P.mul(ans[0],ans[1]);
ans[0].resize(d+1);
ans[0]=P.mul(ans[0],ans[2]);
int ANS=ans[0][d]*C.F[d]%mod;
cout<<ANS<<endl;
}
/*======================================================================*/
signed main()
{
cin.tie(0);
cout.tie(0);
std::ios::sync_with_stdio(false);
//#define Hank2007
#ifdef Hank2007
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
/*====================================================================*/
int TEST_CASE=1;
// cin>>TEST_CASE;
while(TEST_CASE--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 7524kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 2ms
memory: 7544kb
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: 18ms
memory: 8072kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 19ms
memory: 8128kb
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: 716ms
memory: 31416kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 719ms
memory: 31456kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 709ms
memory: 28492kb
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: 725ms
memory: 31624kb
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: 735ms
memory: 28896kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 0
Accepted
time: 731ms
memory: 29052kb
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: 724ms
memory: 33212kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 0
Accepted
time: 717ms
memory: 32040kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: 0
Accepted
time: 713ms
memory: 28444kb
input:
120000 491 495 1 430 25 1
output:
272929924
result:
ok 1 number(s): "272929924"
Test #14:
score: 0
Accepted
time: 744ms
memory: 31244kb
input:
120000 590 593 1 418 459 1
output:
446962505
result:
ok 1 number(s): "446962505"
Test #15:
score: 0
Accepted
time: 751ms
memory: 29148kb
input:
120000 697 690 1 166 450 1
output:
216092107
result:
ok 1 number(s): "216092107"
Test #16:
score: 0
Accepted
time: 746ms
memory: 27028kb
input:
120000 793 799 1 416 61 1
output:
661260042
result:
ok 1 number(s): "661260042"
Test #17:
score: 0
Accepted
time: 753ms
memory: 32976kb
input:
120000 1000 1000 1 613 547 1
output:
429669083
result:
ok 1 number(s): "429669083"
Test #18:
score: 0
Accepted
time: 737ms
memory: 33364kb
input:
120000 1993 1995 1 493 565 1
output:
609392900
result:
ok 1 number(s): "609392900"
Test #19:
score: 0
Accepted
time: 726ms
memory: 29292kb
input:
120000 4995 4998 1 3166 3765 1
output:
394497547
result:
ok 1 number(s): "394497547"
Test #20:
score: 0
Accepted
time: 726ms
memory: 26652kb
input:
120000 9994 9991 1 6099 691 1
output:
795651799
result:
ok 1 number(s): "795651799"
Test #21:
score: 0
Accepted
time: 728ms
memory: 26544kb
input:
120000 49990 49990 1 41933 2862 1
output:
360787513
result:
ok 1 number(s): "360787513"
Test #22:
score: 0
Accepted
time: 731ms
memory: 28480kb
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: 714ms
memory: 26512kb
input:
120000 296 300 297 89 130 280
output:
702788425
result:
ok 1 number(s): "702788425"
Test #24:
score: 0
Accepted
time: 736ms
memory: 28972kb
input:
120000 392 397 391 222 280 10
output:
322470184
result:
ok 1 number(s): "322470184"
Test #25:
score: 0
Accepted
time: 730ms
memory: 26924kb
input:
120000 499 498 500 263 315 367
output:
449848666
result:
ok 1 number(s): "449848666"
Test #26:
score: 0
Accepted
time: 738ms
memory: 31380kb
input:
120000 598 591 594 497 474 400
output:
35486519
result:
ok 1 number(s): "35486519"
Test #27:
score: 0
Accepted
time: 739ms
memory: 31368kb
input:
120000 694 692 695 625 173 477
output:
785203749
result:
ok 1 number(s): "785203749"
Test #28:
score: 0
Accepted
time: 702ms
memory: 28408kb
input:
120000 794 796 800 395 465 507
output:
897269426
result:
ok 1 number(s): "897269426"
Test #29:
score: 0
Accepted
time: 721ms
memory: 31388kb
input:
120000 993 998 991 196 712 911
output:
464727191
result:
ok 1 number(s): "464727191"
Test #30:
score: 0
Accepted
time: 714ms
memory: 33216kb
input:
120000 1991 2000 1994 1937 1362 1494
output:
473701811
result:
ok 1 number(s): "473701811"
Test #31:
score: 0
Accepted
time: 711ms
memory: 31604kb
input:
120000 4994 4990 4990 646 1214 2276
output:
763540821
result:
ok 1 number(s): "763540821"
Test #32:
score: 0
Accepted
time: 706ms
memory: 29836kb
input:
120000 9994 9992 9991 6588 9538 2632
output:
804858722
result:
ok 1 number(s): "804858722"
Test #33:
score: 0
Accepted
time: 801ms
memory: 28472kb
input:
120000 49997 49997 49993 46278 44140 26931
output:
139550295
result:
ok 1 number(s): "139550295"
Test #34:
score: 0
Accepted
time: 735ms
memory: 31352kb
input:
120000 119997 120000 120000 24867 116477 35338
output:
946147605
result:
ok 1 number(s): "946147605"