QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397145 | #6678. Gem Island 2 | zhouhuanyi | AC ✓ | 1084ms | 355336kb | C++14 | 1.4kb | 2024-04-23 17:40:29 | 2024-04-23 17:40:29 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define N 30000000
#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()
{
unsigned long long res;
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<=n;++i) F[i]=1ll*F[i]*C(n,i)%mod;
for (int i=0;i<=d;++i) G[i]=C(n-1+d-i,n-1);
for (int i=1;i<=n;++i)
if (i==1||i>=r+1)
{
res=0;
for (int j=i;j<=d;j+=i) res+=G[j];
Adder(ans,1ll*F[i]*(res%mod)%mod);
}
printf("%d\n",MD(1ll*ans*fast_pow(C(n-1+d,n-1),mod-2)%mod+r));
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 291ms
memory: 238148kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 244ms
memory: 238232kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 263ms
memory: 238144kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 260ms
memory: 238136kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 271ms
memory: 238220kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 257ms
memory: 238196kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 256ms
memory: 238168kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 257ms
memory: 238148kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 261ms
memory: 238604kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 296ms
memory: 245728kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 274ms
memory: 245868kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 302ms
memory: 243772kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 395ms
memory: 355336kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 261ms
memory: 238948kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 293ms
memory: 238924kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 279ms
memory: 238668kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 286ms
memory: 246092kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 297ms
memory: 246004kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 275ms
memory: 242348kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 1084ms
memory: 355336kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 536ms
memory: 355296kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 425ms
memory: 354836kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 262ms
memory: 238152kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 353ms
memory: 355336kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"