QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397138#6678. Gem Island 2zhouhuanyiTL 137ms131560kbC++141.2kb2024-04-23 17:26:442024-04-23 17:26:46

Judging History

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

  • [2024-04-23 17:43:38]
  • hack成功,自动添加数据
  • (/hack/600)
  • [2024-04-23 17:26:46]
  • 评测
  • 测评结果:TL
  • 用时:137ms
  • 内存:131560kb
  • [2024-04-23 17:26:44]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 15000000
#define mod 998244353
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int fast_pow(int a,int b)
{
	int res=1,mul=a;
	while (b)
	{
		if (b&1) res=1ll*res*mul%mod;
		mul=1ll*mul*mul%mod,b>>=1;
	}
	return res;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
void Adder2(int &x,int d)
{
	x+=d;
	if (x<0) x+=mod;
	return;
}
int n,d,r,F[N+1],G[N+1],fac[N+1],invfac[N+1],ans;
int C(int x,int y)
{
	return 1ll*fac[x]*invfac[y]%mod*invfac[x-y]%mod;
}
int main()
{
	fac[0]=1;
	for (int i=1;i<=N;++i) fac[i]=1ll*fac[i-1]*i%mod;
	invfac[N]=fast_pow(fac[N],mod-2);
	for (int i=N-1;i>=0;--i) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
	n=read(),d=read(),r=read(),F[1]=1;
	for (int i=r+1;i<=n;++i)
	{
		if (!((i-r)&1)) F[i]=C(i-2,r-1);
		else F[i]=MD2(-C(i-2,r-1));
	}
	for (int i=1;i<=d;++i)
		for (int j=0;j<=min(n,d/i);++j)
			Adder(ans,1ll*C(n,j)*C(n-1+d-i*j,n-1)%mod*F[j]%mod);
	printf("%d\n",MD(1ll*ans*fast_pow(C(n-1+d,n-1),mod-2)%mod+r));
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 126ms
memory: 124540kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

score: 0
Accepted
time: 128ms
memory: 123660kb

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

score: 0
Accepted
time: 125ms
memory: 123280kb

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

score: 0
Accepted
time: 126ms
memory: 124240kb

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

score: 0
Accepted
time: 129ms
memory: 124932kb

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

score: 0
Accepted
time: 129ms
memory: 124972kb

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

score: 0
Accepted
time: 137ms
memory: 124848kb

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

score: 0
Accepted
time: 133ms
memory: 123892kb

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

score: 0
Accepted
time: 125ms
memory: 124928kb

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

score: 0
Accepted
time: 135ms
memory: 131560kb

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 127ms
memory: 130136kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 134ms
memory: 130608kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: -100
Time Limit Exceeded

input:

14999999 15000000 14999999

output:


result: