QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#628108#8792. CandiesmengzddAC ✓1466ms775896kbC++142.1kb2024-10-10 18:39:032024-10-10 18:39:08

Judging History

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

  • [2024-10-10 18:39:08]
  • 评测
  • 测评结果:AC
  • 用时:1466ms
  • 内存:775896kb
  • [2024-10-10 18:39:03]
  • 提交

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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