QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#204500 | #6678. Gem Island 2 | retaliatorElite | AC ✓ | 794ms | 306472kb | C++14 | 1.6kb | 2023-10-07 12:16:52 | 2024-04-23 17:47:48 |
Judging History
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