QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#204500#6678. Gem Island 2retaliatorEliteAC ✓794ms306472kbC++141.6kb2023-10-07 12:16:522024-04-23 17:47:48

Judging History

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

  • [2024-04-23 17:47:48]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:794ms
  • 内存:306472kb
  • [2024-04-23 17:43:38]
  • hack成功,自动添加数据
  • (/hack/600)
  • [2023-10-07 12:16:52]
  • 评测
  • 测评结果:100
  • 用时:813ms
  • 内存:304488kb
  • [2023-10-07 12:16:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
long long read(){
	long long ret=0,neg=1;
	char c;
	c=getchar();
	while((c<'0'||c>'9')&&c!='-'){
		c=getchar();
	}
	if(c=='-'){
		neg=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		ret=(ret<<1)+(ret<<3)+c-'0';
		c=getchar();
	}
	return ret*neg;
}
void write(long long x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>=10) write(x/10);
	putchar((x%10)+'0');
}
const long long mod=998244353;
int fac[31000000],fic[31000000];
inline long long ksm(long long x,long long t){
	long long ret=1;
	while(t){
		if(t&1){
			ret=ret*x%mod;
		}
		x=x*x%mod;
		t>>=1;
	}
	return ret;
}
inline void Pre(){
	fac[0]=1;
	for(int i=1;i<=30100000;++i){
		fac[i]=1ll*fac[i-1]*i%mod;
	}
	fic[30100000]=ksm(fac[30100000],mod-2);
	for(int i=30100000-1;i>=0;--i){
		fic[i]=1ll*fic[i+1]*(i+1)%mod;
	}
	assert(fic[0]==1);
}
inline long long C(int x,int y){
	if(x<0||y<0||y>x) return 0;
	return 1ll*fac[x]*fic[y]%mod*fic[x-y]%mod;
}
int n,D,r;
int f[16000000];
bitset<16000000> vis;
inline void Get_f(){
	f[0]=1ll*D*C(D+n-1,n-1)%mod;
	for(int i=1;i<=D;++i)
		f[i]=C(D-i+n-1,n-1);
	for(int i=2;i<=D;++i){
		if(vis[i]==false){
			for(int j=(D/i);j;--j){
				vis[i*j]=true;
				f[j]=(f[j]+f[i*j])%mod;
			}
		}
	}
}
int main(){
	Pre();
	n=read();
	D=read();
	r=read();
	Get_f();
	int ans=0;
	for(int j=0;j<=n;++j){
		int tmp;
		if((j+r)&1) tmp=mod-1;
		else tmp=1;
		tmp=1ll*tmp*C(n,j)%mod*f[j]%mod*C(j-2,r-1)%mod;
		ans=(ans+tmp)%mod;
	}
	ans=1ll*ans*fac[D]%mod*fac[n-1]%mod*fic[n+D-1]%mod;
	ans+=r+D;
	ans%=mod;
	write(ans);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 245ms
memory: 245320kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

score: 0
Accepted
time: 267ms
memory: 243192kb

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

score: 0
Accepted
time: 246ms
memory: 245300kb

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

score: 0
Accepted
time: 254ms
memory: 243252kb

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

score: 0
Accepted
time: 241ms
memory: 243316kb

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

score: 0
Accepted
time: 239ms
memory: 245260kb

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

score: 0
Accepted
time: 241ms
memory: 245180kb

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

score: 0
Accepted
time: 246ms
memory: 243180kb

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

score: 0
Accepted
time: 255ms
memory: 245240kb

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

score: 0
Accepted
time: 277ms
memory: 243256kb

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 259ms
memory: 247352kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 280ms
memory: 243256kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: 0
Accepted
time: 659ms
memory: 306472kb

input:

14999999 15000000 14999999

output:

29999999

result:

ok 1 number(s): "29999999"

Test #14:

score: 0
Accepted
time: 260ms
memory: 245376kb

input:

98765 99654 85647

output:

815183913

result:

ok 1 number(s): "815183913"

Test #15:

score: 0
Accepted
time: 257ms
memory: 247380kb

input:

99999 100000 99998

output:

832290200

result:

ok 1 number(s): "832290200"

Test #16:

score: 0
Accepted
time: 251ms
memory: 247240kb

input:

1541 99998 725

output:

463021366

result:

ok 1 number(s): "463021366"

Test #17:

score: 0
Accepted
time: 281ms
memory: 251568kb

input:

985438 998756 101254

output:

671487608

result:

ok 1 number(s): "671487608"

Test #18:

score: 0
Accepted
time: 271ms
memory: 247532kb

input:

998654 999856 2

output:

92085960

result:

ok 1 number(s): "92085960"

Test #19:

score: 0
Accepted
time: 262ms
memory: 247524kb

input:

45876 1000000 13

output:

208089291

result:

ok 1 number(s): "208089291"

Test #20:

score: 0
Accepted
time: 789ms
memory: 304492kb

input:

15000000 14999999 514

output:

143843956

result:

ok 1 number(s): "143843956"

Test #21:

score: 0
Accepted
time: 794ms
memory: 306332kb

input:

14985345 14999998 145124

output:

785676527

result:

ok 1 number(s): "785676527"

Test #22:

score: 0
Accepted
time: 765ms
memory: 302868kb

input:

14855345 14993298 1451424

output:

779861797

result:

ok 1 number(s): "779861797"

Test #23:

score: 0
Accepted
time: 253ms
memory: 243336kb

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #24:

score: 0
Accepted
time: 659ms
memory: 303584kb

input:

15000000 15000000 15000000

output:

30000000

result:

ok 1 number(s): "30000000"

Extra Test:

score: 0
Extra Test Passed