QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#628108 | #8792. Candies | mengzdd | AC ✓ | 1466ms | 775896kb | C++14 | 2.1kb | 2024-10-10 18:39:03 | 2024-10-10 18:39:08 |
Judging History
answer
#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=(j);i<=(k);++i)
#define NFOR(i,j,k) for(int i=(j);i>=(k);--i)
#define mkp make_pair
#define fst first
#define sec second
#define inl inline
#define pb push_back
#define el_phy_kongroo return 0
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned int ui;
typedef pair< int,int > pii;
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+ch-'0',ch=getchar();}
return s*w;
}
void file()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
void teltim(int x)
{
clock_t c1=0;
if(x) c1=clock();
else cerr<<endl<<clock()-c1<<"ms"<<endl;
}
const int N=3e4+10;
const ll mod=998244353;
int a,b,c;
namespace permutation
{
ll fac[N],inv[N],facinv[N];
bool hasinit;
void init()
{
hasinit=1;
fac[0]=fac[1]=inv[1]=facinv[0]=facinv[1]=1;
FOR(i,2,N-2)
{
inv[i]=mod-mod/i*inv[mod%i]%mod;
fac[i]=fac[i-1]*i%mod;
facinv[i]=facinv[i-1]*inv[i]%mod;
}
}
inl int C(int x,int y)
{
if(!hasinit) init();
return fac[x]*facinv[y]%mod*facinv[x-y]%mod;
}
inl int C(int x,int y,int z)
{
if(!hasinit) init();
if(x<0||y<0||z<0) return 0;
return fac[x+y+z]*facinv[x]%mod*facinv[y]%mod*facinv[z]%mod;
}
}
using namespace permutation;
const int n=1e4+5;
ll ans;
ll dp[n][n];
int main()
{
//file();
FOR(i,0,n-3) dp[i][0]=C(i<<1|1,i)*inv[i<<1|1]%mod;
FOR(i,1,n-3)
{
FOR(j,1,i-1) dp[i][j]=(dp[i-1][j]+dp[j][j])%mod;
dp[i][i]=2*inv[i]%mod;
}
FOR(i,1,n-3)
{
int tmp1=i<<1|1,tmp2=i<<1|1;
ll tmp=dp[i][0];
FOR(j,1,i)
{
ll coef=tmp1*inv[tmp2]%mod;
tmp=tmp*dp[i][j]%mod*coef%mod;
dp[i][j]=tmp;
tmp1++,tmp2-=2;
}
}
a=read(),b=read(),c=read();
ans=C(a,b,c)%mod;
//printf("%lld\n",ans);
FOR(i,0,b-1) FOR(j,0,min(i,c))
{
ll sto=C(a-i,b-i-1,c-j)*dp[i][j]%mod;
ans=(ans-sto+mod)%mod;
//printf("%lld %lld\n",C(a-i,b-i-1,c-j),dp[i][j]);
}
FOR(j,0,c-1) FOR(i,0,min(j,b))
{
ll sto=C(a-j,b-i,c-j-1)*dp[j][i]%mod;
ans=(ans-sto+mod)%mod;
//printf("%lld %lld\n",C(a-j,b-i,c-j-1),dp[j][i]);
}
printf("%lld",(ans+mod)%mod);
el_phy_kongroo;
}
/*
10000 10000 10000
*/
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 704ms
memory: 598908kb
input:
4 3 2
output:
368
result:
ok answer is '368'
Test #2:
score: 0
Accepted
time: 1466ms
memory: 623176kb
input:
10000 10000 10000
output:
905642282
result:
ok answer is '905642282'
Test #3:
score: 0
Accepted
time: 665ms
memory: 633808kb
input:
99 99 99
output:
604759627
result:
ok answer is '604759627'
Test #4:
score: 0
Accepted
time: 1178ms
memory: 643436kb
input:
10000 9876 6543
output:
172894229
result:
ok answer is '172894229'
Test #5:
score: 0
Accepted
time: 553ms
memory: 707564kb
input:
7 1 6
output:
5577
result:
ok answer is '5577'
Test #6:
score: 0
Accepted
time: 548ms
memory: 713512kb
input:
28 23 17
output:
816429586
result:
ok answer is '816429586'
Test #7:
score: 0
Accepted
time: 516ms
memory: 743408kb
input:
87 54 22
output:
401507657
result:
ok answer is '401507657'
Test #8:
score: 0
Accepted
time: 522ms
memory: 747288kb
input:
50 40 16
output:
770938562
result:
ok answer is '770938562'
Test #9:
score: 0
Accepted
time: 506ms
memory: 753132kb
input:
72 19 53
output:
607733148
result:
ok answer is '607733148'
Test #10:
score: 0
Accepted
time: 492ms
memory: 770048kb
input:
8 4 4
output:
325590
result:
ok answer is '325590'
Test #11:
score: 0
Accepted
time: 490ms
memory: 772764kb
input:
65 45 14
output:
452076388
result:
ok answer is '452076388'
Test #12:
score: 0
Accepted
time: 486ms
memory: 773052kb
input:
82 8 67
output:
708832480
result:
ok answer is '708832480'
Test #13:
score: 0
Accepted
time: 467ms
memory: 774388kb
input:
65 10 35
output:
769016918
result:
ok answer is '769016918'
Test #14:
score: 0
Accepted
time: 493ms
memory: 774476kb
input:
4 3 4
output:
1408
result:
ok answer is '1408'
Test #15:
score: 0
Accepted
time: 495ms
memory: 774136kb
input:
9139 6356 279
output:
833879698
result:
ok answer is '833879698'
Test #16:
score: 0
Accepted
time: 537ms
memory: 774208kb
input:
3888 2407 1937
output:
380556889
result:
ok answer is '380556889'
Test #17:
score: 0
Accepted
time: 669ms
memory: 774044kb
input:
9161 3171 7913
output:
643956900
result:
ok answer is '643956900'
Test #18:
score: 0
Accepted
time: 483ms
memory: 774848kb
input:
1392 1354 938
output:
491399135
result:
ok answer is '491399135'
Test #19:
score: 0
Accepted
time: 481ms
memory: 774612kb
input:
5930 427 1403
output:
786969030
result:
ok answer is '786969030'
Test #20:
score: 0
Accepted
time: 471ms
memory: 775416kb
input:
507 99 150
output:
960656496
result:
ok answer is '960656496'
Test #21:
score: 0
Accepted
time: 530ms
memory: 775736kb
input:
3119 2372 2681
output:
751161512
result:
ok answer is '751161512'
Test #22:
score: 0
Accepted
time: 573ms
memory: 775780kb
input:
6636 3688 2743
output:
839083240
result:
ok answer is '839083240'
Test #23:
score: 0
Accepted
time: 493ms
memory: 774888kb
input:
4890 475 2865
output:
788640273
result:
ok answer is '788640273'
Test #24:
score: 0
Accepted
time: 504ms
memory: 775896kb
input:
6708 663 6384
output:
426276232
result:
ok answer is '426276232'
Test #25:
score: 0
Accepted
time: 479ms
memory: 775652kb
input:
1 1 1
output:
2
result:
ok answer is '2'
Extra Test:
score: 0
Extra Test Passed