QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492673 | #8792. Candies | ucup-team3924 | AC ✓ | 3130ms | 4016kb | C++23 | 1.8kb | 2024-07-26 15:09:07 | 2024-07-26 15:09:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define sq(x) (x)*(x)
const int MOD = 998244353;
struct ModInt{
int x;
ModInt(int x = 0) : x(x + (x < 0) * MOD - (x >= MOD) * MOD){}
ModInt operator+(ModInt o) { return x + o.x; }
ModInt operator-(ModInt o) { return x - o.x; }
ModInt operator*(ModInt o) { return 1LL * x * o.x % MOD; }
ModInt operator/(ModInt b) { return *this * b.inv(); }
ModInt inv() { return pow(MOD-2); }
ModInt pow(long long e){
if(!e)return 1;
ModInt r = pow(e/2); r = r * r;
return e % 2 ? *this * r : r;
}
bool operator==(ModInt o) { return x == o.x; }
};
const int maxn = 40000;
ModInt factorial[maxn+1];
ModInt invfactorial[maxn+1];
//ModInt
ModInt binom(int n, int k){
if(n < 0 || k < 0 || n < k)return 0;
return factorial[n]*invfactorial[n-k]*invfactorial[k];
}
ModInt invbinom(int n, int k){
if(n < 0 || k < 0 || n < k)return 0;
return invfactorial[n]*factorial[n-k]*factorial[k];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
factorial[0] = 1;
for(int i = 1; i <= maxn; i++)factorial[i] = factorial[i-1]*i;
invfactorial[maxn] = factorial[maxn].inv();
for(int i = maxn-1; i >= 0; i--)invfactorial[i] = invfactorial[i+1]*(i+1);
int q, r, s;
cin >> s >> r >> q;
ModInt Kreweras= 0;
for(int i = 1; i <= q; i++){
for(int j = 1; j <= r; j++){
if((i+j)%2 == 0) Kreweras = Kreweras + binom(q,i)*binom(r,j)*binom(2*(i+j-1),2*i-1)*invbinom(i+j+s, s+2);
else Kreweras = Kreweras - binom(q,i)*binom(r,j)*binom(2*(i+j-1),2*i-1)*invbinom(i+j+s, s+2);
}
}
Kreweras = Kreweras * ModInt(1)/(ModInt(s+1)*ModInt(s+2));
Kreweras = Kreweras - ModInt(q+r)/ModInt(s+1);
Kreweras = Kreweras + ModInt(1);
ModInt total = binom(q + r + s, q)*binom(r+s, r);
Kreweras = Kreweras * total;
cout << Kreweras.x << '\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4008kb
input:
4 3 2
output:
368
result:
ok answer is '368'
Test #2:
score: 0
Accepted
time: 3130ms
memory: 3948kb
input:
10000 10000 10000
output:
905642282
result:
ok answer is '905642282'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
99 99 99
output:
604759627
result:
ok answer is '604759627'
Test #4:
score: 0
Accepted
time: 2020ms
memory: 3864kb
input:
10000 9876 6543
output:
172894229
result:
ok answer is '172894229'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
7 1 6
output:
5577
result:
ok answer is '5577'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4016kb
input:
28 23 17
output:
816429586
result:
ok answer is '816429586'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
87 54 22
output:
401507657
result:
ok answer is '401507657'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3940kb
input:
50 40 16
output:
770938562
result:
ok answer is '770938562'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3956kb
input:
72 19 53
output:
607733148
result:
ok answer is '607733148'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3948kb
input:
8 4 4
output:
325590
result:
ok answer is '325590'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
65 45 14
output:
452076388
result:
ok answer is '452076388'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3948kb
input:
82 8 67
output:
708832480
result:
ok answer is '708832480'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
65 10 35
output:
769016918
result:
ok answer is '769016918'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
4 3 4
output:
1408
result:
ok answer is '1408'
Test #15:
score: 0
Accepted
time: 53ms
memory: 3936kb
input:
9139 6356 279
output:
833879698
result:
ok answer is '833879698'
Test #16:
score: 0
Accepted
time: 146ms
memory: 3856kb
input:
3888 2407 1937
output:
380556889
result:
ok answer is '380556889'
Test #17:
score: 0
Accepted
time: 781ms
memory: 3940kb
input:
9161 3171 7913
output:
643956900
result:
ok answer is '643956900'
Test #18:
score: 0
Accepted
time: 41ms
memory: 3884kb
input:
1392 1354 938
output:
491399135
result:
ok answer is '491399135'
Test #19:
score: 0
Accepted
time: 20ms
memory: 3996kb
input:
5930 427 1403
output:
786969030
result:
ok answer is '786969030'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
507 99 150
output:
960656496
result:
ok answer is '960656496'
Test #21:
score: 0
Accepted
time: 197ms
memory: 3860kb
input:
3119 2372 2681
output:
751161512
result:
ok answer is '751161512'
Test #22:
score: 0
Accepted
time: 313ms
memory: 3948kb
input:
6636 3688 2743
output:
839083240
result:
ok answer is '839083240'
Test #23:
score: 0
Accepted
time: 43ms
memory: 4012kb
input:
4890 475 2865
output:
788640273
result:
ok answer is '788640273'
Test #24:
score: 0
Accepted
time: 133ms
memory: 3944kb
input:
6708 663 6384
output:
426276232
result:
ok answer is '426276232'
Test #25:
score: 0
Accepted
time: 1ms
memory: 4016kb
input:
1 1 1
output:
2
result:
ok answer is '2'
Extra Test:
score: 0
Extra Test Passed