QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91664 | #4903. 细菌 | Walking_Dead | 100 ✓ | 1008ms | 57236kb | C++14 | 4.8kb | 2023-03-29 11:48:27 | 2023-03-29 11:48:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
#define MAXN 2000005
// char buf[1<<21],*p1=buf,*p2=buf;
// #define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> inline void chkmax (T &a,T b){a = max (a,b);}
template <typename T> inline void chkmin (T &a,T b){a = min (a,b);}
int D,N,M,K,X,Y,Z;
int fac[MAXN],ifac[MAXN];
int sqr (int x){return 1ll * x * x % mod;}
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
int qkpow (int a,int b){
int res = 1;for (;b;b >>= 1,a = mul (a,a)) if (b & 1) res = mul (res,a);
return res;
}
void Add (int &a,int b){a = add (a,b);}
void Sub (int &a,int b){a = dec (a,b);}
int binom (int a,int b){return a >= b ? mul (fac[a],mul (ifac[b],ifac[a - b])) : 0;}
int getit (int t,int k){//走t步,位移量为k的方案数
if (t + k & 1) return 0;
int s = t + k >> 1;
if (s < 0 || s > t) return 0;
return binom (t,s);
}
typedef vector<int> poly;
int w[MAXN],rev[MAXN];
#define SZ(A) ((int)A.size())
void init_ntt (){
int lim = 1 << 20;
for (int i = 0;i < lim;++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << 19);
int Wn = qkpow (3,(mod - 1) / lim);w[lim >> 1] = 1;
for (int i = lim / 2 + 1;i < lim;++ i) w[i] = mul (w[i - 1],Wn);
for (int i = lim / 2 - 1;i;-- i) w[i] = w[i << 1];
}
void ntt (poly &a,int type){
#define G 3
#define Gi 332748118
static int d[MAXN];int lim = a.size();
for (int i = 0,z = 20 - __builtin_ctz(lim);i < lim;++ i) d[rev[i] >> z] = a[i];
for (int i = 1;i < lim;i <<= 1)
for (int j = 0;j < lim;j += i << 1)
for (int k = 0;k < i;++ k){
int x = mul (w[i + k],d[i + j + k]);
d[i + j + k] = dec (d[j + k],x),d[j + k] = add (d[j + k],x);
}
for (int i = 0;i < lim;++ i) a[i] = d[i] % mod;
if (type == -1){
reverse (a.begin() + 1,a.begin() + lim);
for (int i = 0,Inv = qkpow (lim,mod - 2);i < lim;++ i) a[i] = mul (a[i],Inv);
}
#undef G
#undef Gi
}
poly operator * (poly A,poly B){
int lim = 1,l = 0,len = SZ(A) + SZ(B) - 1;
while (lim < SZ(A) + SZ(B)) lim <<= 1,++ l;
A.resize (lim),B.resize (lim),ntt (A,1),ntt (B,1);
for (int i = 0;i < lim;++ i) A[i] = mul (A[i],B[i]);
ntt (A,-1),A.resize (len);
return A;
}
int f0[MAXN],g0[MAXN],res[MAXN],tl[MAXN],tr[MAXN];
int countit (int t,int L,int R){
int nowl = tl[t],nowr = tr[t],ans = res[t];
while (nowl > L) -- nowl,Add (ans,binom (t,nowl));
while (nowl < L) Sub (ans,binom (t,nowl)),nowl ++;
while (nowr < R) ++ nowr,Add (ans,binom (t,nowr));
while (nowr > R) Sub (ans,binom (t,nowr)),nowr --;
return ans;
}
void divide (int n,int L,int R){
if (L == R) return ;
int mid = L + R >> 1;
divide (n,L,mid);
poly F,G;int len = R - L + 1;F.resize (len + 1),G.resize (mid - L + 1);
for (int j = 0;j <= len;++ j) F[j] = add (getit (j,-1),getit (j,n));
for (int j = 0;j <= mid - L;++ j) G[j] = g0[L + j];
F = F * G;
for (int j = mid + 1;j <= R;++ j) Sub (g0[j],F[j - L - 1]);
divide (n,mid + 1,R);
}
poly work (int n,int beg){
f0[0] = g0[0] = res[0] = 1;
for (int i = 0;i <= D;++ i) tl[i] = (i + 1) >> 1,tr[i] = (i + n - 1) >> 1;
for (int i = 1;i <= D;++ i) g0[i] = add (countit (i - 1,tl[i] - 1,tr[i] - 1),countit (i - 1,tl[i],tr[i])),res[i] = g0[i];
divide (n,0,D);
for (int i = 0;i <= D;++ i){
tl[i] = i - beg + 1,tr[i] = i - beg + n;
if (tl[i] & 1) tl[i] ++;if (tr[i] & 1) tr[i] --;
tl[i] >>= 1,tr[i] >>= 1,chkmax (tl[i],0);
}
for (int i = 1;i <= D;++ i) f0[i] = add (countit (i - 1,tl[i] - 1,tr[i] - 1),countit (i - 1,tl[i],tr[i])),res[i] = f0[i];
poly F,G;F.resize (D + 1),G.resize (D + 1);
for (int j = 0;j <= D;++ j) F[j] = add (getit (j,0 - beg),getit (j,n + 1 - beg)),G[j] = g0[j];
F = F * G;
for (int i = 1;i <= D;++ i) Sub (f0[i],F[i - 1]);
poly Now;Now.resize (D + 1);
for (int i = 0;i <= D;++ i) Now[i] = mul (f0[i],ifac[i]);
return Now;
}
signed main(){
read (D,N,M,K,X,Y,Z),init_ntt ();
int up = 2e6;
fac[0] = 1;for (int i = 1;i <= up;++ i) fac[i] = mul (fac[i - 1],i);
ifac[up] = qkpow (fac[up],mod - 2);for (int i = up;i;-- i) ifac[i - 1] = mul (ifac[i],i);
poly F1 = work (N,X),F2 = work (M,Y),F3 = work (K,Z);
F1 = F1 * F2 * F3,write (mul (F1[D],fac[D])),putchar ('\n');
return 0;
}
/*
120000 300 1 1 141 1 1
*/
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 15ms
memory: 42104kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 25ms
memory: 39272kb
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: 50ms
memory: 41944kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 49ms
memory: 41268kb
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: 992ms
memory: 54372kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 992ms
memory: 57236kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 983ms
memory: 52600kb
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: 1008ms
memory: 52372kb
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: 996ms
memory: 55500kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 0
Accepted
time: 983ms
memory: 53988kb
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: 994ms
memory: 54372kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 0
Accepted
time: 995ms
memory: 54848kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: 0
Accepted
time: 984ms
memory: 57116kb
input:
120000 491 495 1 430 25 1
output:
272929924
result:
ok 1 number(s): "272929924"
Test #14:
score: 0
Accepted
time: 989ms
memory: 55136kb
input:
120000 590 593 1 418 459 1
output:
446962505
result:
ok 1 number(s): "446962505"
Test #15:
score: 0
Accepted
time: 985ms
memory: 53836kb
input:
120000 697 690 1 166 450 1
output:
216092107
result:
ok 1 number(s): "216092107"
Test #16:
score: 0
Accepted
time: 1000ms
memory: 53368kb
input:
120000 793 799 1 416 61 1
output:
661260042
result:
ok 1 number(s): "661260042"
Test #17:
score: 0
Accepted
time: 991ms
memory: 52756kb
input:
120000 1000 1000 1 613 547 1
output:
429669083
result:
ok 1 number(s): "429669083"
Test #18:
score: 0
Accepted
time: 1007ms
memory: 55408kb
input:
120000 1993 1995 1 493 565 1
output:
609392900
result:
ok 1 number(s): "609392900"
Test #19:
score: 0
Accepted
time: 1000ms
memory: 54420kb
input:
120000 4995 4998 1 3166 3765 1
output:
394497547
result:
ok 1 number(s): "394497547"
Test #20:
score: 0
Accepted
time: 987ms
memory: 53580kb
input:
120000 9994 9991 1 6099 691 1
output:
795651799
result:
ok 1 number(s): "795651799"
Test #21:
score: 0
Accepted
time: 985ms
memory: 52484kb
input:
120000 49990 49990 1 41933 2862 1
output:
360787513
result:
ok 1 number(s): "360787513"
Test #22:
score: 0
Accepted
time: 1007ms
memory: 52396kb
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: 981ms
memory: 55248kb
input:
120000 296 300 297 89 130 280
output:
702788425
result:
ok 1 number(s): "702788425"
Test #24:
score: 0
Accepted
time: 976ms
memory: 52400kb
input:
120000 392 397 391 222 280 10
output:
322470184
result:
ok 1 number(s): "322470184"
Test #25:
score: 0
Accepted
time: 985ms
memory: 53928kb
input:
120000 499 498 500 263 315 367
output:
449848666
result:
ok 1 number(s): "449848666"
Test #26:
score: 0
Accepted
time: 991ms
memory: 55120kb
input:
120000 598 591 594 497 474 400
output:
35486519
result:
ok 1 number(s): "35486519"
Test #27:
score: 0
Accepted
time: 982ms
memory: 57168kb
input:
120000 694 692 695 625 173 477
output:
785203749
result:
ok 1 number(s): "785203749"
Test #28:
score: 0
Accepted
time: 958ms
memory: 54096kb
input:
120000 794 796 800 395 465 507
output:
897269426
result:
ok 1 number(s): "897269426"
Test #29:
score: 0
Accepted
time: 986ms
memory: 55464kb
input:
120000 993 998 991 196 712 911
output:
464727191
result:
ok 1 number(s): "464727191"
Test #30:
score: 0
Accepted
time: 990ms
memory: 57156kb
input:
120000 1991 2000 1994 1937 1362 1494
output:
473701811
result:
ok 1 number(s): "473701811"
Test #31:
score: 0
Accepted
time: 981ms
memory: 54856kb
input:
120000 4994 4990 4990 646 1214 2276
output:
763540821
result:
ok 1 number(s): "763540821"
Test #32:
score: 0
Accepted
time: 982ms
memory: 57116kb
input:
120000 9994 9992 9991 6588 9538 2632
output:
804858722
result:
ok 1 number(s): "804858722"
Test #33:
score: 0
Accepted
time: 995ms
memory: 55200kb
input:
120000 49997 49997 49993 46278 44140 26931
output:
139550295
result:
ok 1 number(s): "139550295"
Test #34:
score: 0
Accepted
time: 996ms
memory: 57148kb
input:
120000 119997 120000 120000 24867 116477 35338
output:
946147605
result:
ok 1 number(s): "946147605"