QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91656#4903. 细菌Walking_Dead15 541ms20260kbC++144.0kb2023-03-29 11:25:582023-03-29 11:26: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-03-29 11:26:02]
  • 评测
  • 测评结果:15
  • 用时:541ms
  • 内存:20260kb
  • [2023-03-29 11:25:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define mod 998244353
#define MAXN 800005

// 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 << 18;
	for (int i = 0;i < lim;++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << 17);
	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 = 18 - __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];
poly work (int n,int beg){
	f0[0] = g0[0] = 1;
	for (int i = 1;i <= D;++ i){
		g0[i] = 0;
		int l = (i + 1) >> 1,r = (i + n - 1) >> 1;
		for (int j = l;j <= r;++ j) Add (g0[i],binom (i,j));
	}
	for (int i = 1;i <= D;++ i){
		for (int j = 0,v;j < i;++ j){
			v = getit (j,0 - 1);
			if (v) Sub (g0[i],mul (v,g0[i - j - 1]));
			v = getit (j,n);
			if (v) Sub (g0[i],mul (v,g0[i - j - 1]));
		}
	}
	for (int i = 1;i <= D;++ i){
		f0[i] = 0;
		for (int j = 1;j <= n;++ j) Add (f0[i],getit (i,j - beg));
		for (int j = 0,v;j < i;++ j){
			v = getit (j,0 - beg);
			if (v) Sub (f0[i],mul (v,g0[i - j - 1]));
			v = getit (j,n + 1 - beg);
			if (v) Sub (f0[i],mul (v,g0[i - j - 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 = 8e5;
	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;
}
/*
??
??
1
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 10ms
memory: 18816kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 13ms
memory: 18116kb

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: 541ms
memory: 20260kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 534ms
memory: 18728kb

input:

5000 4994 4997 4994 4399 1826 1332

output:

65414465

result:

ok 1 number(s): "65414465"

Subtask #3:

score: 0
Time Limit Exceeded

Test #5:

score: 0
Time Limit Exceeded

input:

120000 300 1 1 141 1 1

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #8:

score: 0
Time Limit Exceeded

input:

119000 119991 119991 1 23819 52139 1

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #3:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%