QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#577414#8792. Candiesmyusername#AC ✓1278ms395440kbC++142.3kb2024-09-20 11:13:022024-09-20 11:13:02

Judging History

你现在查看的是最新测评结果

  • [2024-09-20 11:13:02]
  • 评测
  • 测评结果:AC
  • 用时:1278ms
  • 内存:395440kb
  • [2024-09-20 11:13:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int qpow(int a,int b){
	int res = 1;
	for( ; b; b >>= 1){
		if(b & 1) res = 1LL * res * a % MOD;
		a = 1LL * a * a % MOD;
	}
	return res;
}
/*
struct edge{
	int to,nxt;
}e[200010];
int nE = 0,hd[200010];
void add(int u,int v){
	e[++nE] = (edge){v,hd[u]};
	hd[u] = ++nE;
}
int fa[200010];
int Find(int i){
	return fa[i] == i ? i : fa[i] = Find(fa[i]);
}
void Unite(int u,int v){
	u = Find(u),v = Find(v);
	if(u == v) return;
	fa[u] = v;
}
int bit[200010];
int LSB(int i){
	return i & (-i);
}
void upd(int i,int v){
	while(i <= n){
		bit[i] += v;
		i += LSB(i);
	}
}
int psq(int i){
	int res = 0;
	while(i){
		res += bit[i];
		i -= LSB(i);
	}
}
*/
int x,y,z;
int f[10010][10010],fac[30010],ifac[30010],inv[30010];
int C(int a,int b,int c){
	if(a < 0 || b < 0 || c < 0) return 0;
	return 1LL * fac[a + b + c] * ifac[a] % MOD * ifac[b] % MOD * ifac[c] % MOD;
}
int main(){
	fac[0] = 1;
	for(int i = 1; i < 30010; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;
	ifac[30009] = qpow(fac[30009],MOD - 2);
	for(int i = 30008; i >= 0; i--) ifac[i] = 1LL * ifac[i + 1] * (i + 1) % MOD;
	for(int i = 0; i <= 10002; i++) f[i][0] = 1LL * fac[2 * i] * ifac[i] % MOD * ifac[i + 1] % MOD;
	inv[1] = 1;
	for(int i = 2; i < 30010; i++) inv[i] = 1LL * (MOD - MOD / i) * inv[MOD % i] % MOD;
	for(int i = 1; i <= 10002; i++){
		for(int j = 1; j < i; j++) f[i][j] = (f[i - 1][j] + f[j][j]) % MOD;
		f[i][i] = 2LL * inv[i] % MOD;
	}
	for(int i = 1; i <= 10002; i++){
		int tmp1 = 2 * i + 1,tmp2 = 2 * i + 1,tmp = f[i][0];
		for(int j = 1; j <= i; j++){
			int coef = 1LL * tmp1 * inv[tmp2] % MOD;
			tmp = 1LL * tmp * f[i][j] % MOD * coef % MOD;
			f[i][j] = tmp;
			tmp1++,tmp2 -= 2;
		}
	}
	scanf("%d %d %d",&x,&y,&z);
	int ans = C(x,y,z);
	//(a,a,b)
	for(int a = 0; a + 1 <= y; a++){
		for(int b = 0; b <= min(a,z); b++){
			//(a,a + 1,b)
			int coef = 1LL * f[a][b] * C(x - a,y - a - 1,z - b) % MOD;
			ans = (ans - coef) % MOD;
		}
	}
	//(b,a,b)
	for(int b = 0; b + 1 <= z; b++){
		for(int a = 0; a <= min(b,y); a++){
			//(b,a,b + 1)
			int coef = 1LL * f[b][a] * C(x - b,y - a,z - b - 1) % MOD;
			ans = (ans - coef) % MOD;
		}
	}
	printf("%d",(ans + MOD) % MOD);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 467ms
memory: 394816kb

input:

4 3 2

output:

368

result:

ok answer is '368'

Test #2:

score: 0
Accepted
time: 1278ms
memory: 394656kb

input:

10000 10000 10000

output:

905642282

result:

ok answer is '905642282'

Test #3:

score: 0
Accepted
time: 459ms
memory: 394620kb

input:

99 99 99

output:

604759627

result:

ok answer is '604759627'

Test #4:

score: 0
Accepted
time: 993ms
memory: 394960kb

input:

10000 9876 6543

output:

172894229

result:

ok answer is '172894229'

Test #5:

score: 0
Accepted
time: 460ms
memory: 394056kb

input:

7 1 6

output:

5577

result:

ok answer is '5577'

Test #6:

score: 0
Accepted
time: 463ms
memory: 394172kb

input:

28 23 17

output:

816429586

result:

ok answer is '816429586'

Test #7:

score: 0
Accepted
time: 464ms
memory: 394188kb

input:

87 54 22

output:

401507657

result:

ok answer is '401507657'

Test #8:

score: 0
Accepted
time: 464ms
memory: 395388kb

input:

50 40 16

output:

770938562

result:

ok answer is '770938562'

Test #9:

score: 0
Accepted
time: 467ms
memory: 394620kb

input:

72 19 53

output:

607733148

result:

ok answer is '607733148'

Test #10:

score: 0
Accepted
time: 461ms
memory: 395272kb

input:

8 4 4

output:

325590

result:

ok answer is '325590'

Test #11:

score: 0
Accepted
time: 463ms
memory: 395440kb

input:

65 45 14

output:

452076388

result:

ok answer is '452076388'

Test #12:

score: 0
Accepted
time: 462ms
memory: 395128kb

input:

82 8 67

output:

708832480

result:

ok answer is '708832480'

Test #13:

score: 0
Accepted
time: 461ms
memory: 394292kb

input:

65 10 35

output:

769016918

result:

ok answer is '769016918'

Test #14:

score: 0
Accepted
time: 466ms
memory: 393904kb

input:

4 3 4

output:

1408

result:

ok answer is '1408'

Test #15:

score: 0
Accepted
time: 477ms
memory: 394060kb

input:

9139 6356 279

output:

833879698

result:

ok answer is '833879698'

Test #16:

score: 0
Accepted
time: 501ms
memory: 395368kb

input:

3888 2407 1937

output:

380556889

result:

ok answer is '380556889'

Test #17:

score: 0
Accepted
time: 662ms
memory: 394732kb

input:

9161 3171 7913

output:

643956900

result:

ok answer is '643956900'

Test #18:

score: 0
Accepted
time: 469ms
memory: 394696kb

input:

1392 1354 938

output:

491399135

result:

ok answer is '491399135'

Test #19:

score: 0
Accepted
time: 468ms
memory: 394516kb

input:

5930 427 1403

output:

786969030

result:

ok answer is '786969030'

Test #20:

score: 0
Accepted
time: 463ms
memory: 395280kb

input:

507 99 150

output:

960656496

result:

ok answer is '960656496'

Test #21:

score: 0
Accepted
time: 511ms
memory: 395256kb

input:

3119 2372 2681

output:

751161512

result:

ok answer is '751161512'

Test #22:

score: 0
Accepted
time: 540ms
memory: 395392kb

input:

6636 3688 2743

output:

839083240

result:

ok answer is '839083240'

Test #23:

score: 0
Accepted
time: 472ms
memory: 394800kb

input:

4890 475 2865

output:

788640273

result:

ok answer is '788640273'

Test #24:

score: 0
Accepted
time: 497ms
memory: 394896kb

input:

6708 663 6384

output:

426276232

result:

ok answer is '426276232'

Test #25:

score: 0
Accepted
time: 458ms
memory: 394308kb

input:

1 1 1

output:

2

result:

ok answer is '2'

Extra Test:

score: 0
Extra Test Passed