QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#577414 | #8792. Candies | myusername# | AC ✓ | 1278ms | 395440kb | C++14 | 2.3kb | 2024-09-20 11:13:02 | 2024-09-20 11:13:02 |
Judging History
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,我给组数据试试?
详细
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