QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#417665 | #6678. Gem Island 2 | IDontKnowGoodNames | AC ✓ | 1022ms | 846420kb | C++17 | 1.2kb | 2024-05-22 20:34:57 | 2024-05-22 20:34:59 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops,inline")
#include<bits/stdc++.h>
using namespace std;
const int NR=1.5e7+10;
#define int long long
const int MOD=998244353;
int n,d,r,fac[NR*2],inv[NR*2],ifac[NR*2],f[NR],prime[NR],tot;
bool vis[NR];
void add(int &x,int y){x=(x+y)%MOD;}
void init(){
for(int i=2;i<NR;i++){
if(!vis[i])prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<NR;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int C(int x,int y){return fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}
signed main(){
// freopen("count.in","r",stdin);
// freopen("count.out","w",stdout);
cin>>n>>d>>r;init();
inv[1]=1;
for(int i=2;i<=n+d;i++)inv[i]=(MOD-inv[MOD%i])*(MOD/i)%MOD;
fac[0]=ifac[0]=1;
for(int i=1;i<=n+d;i++)
fac[i]=fac[i-1]*i%MOD,ifac[i]=ifac[i-1]*inv[i]%MOD;
int ans=0;
for(int i=1;i<=d;i++)f[i]=C(d-i+n-1,n-1);
for(int i=1;i<=tot;i++)
for(int j=d/prime[i];j>=1;j--)f[j]=(f[j]+f[j*prime[i]])%MOD;
for(int i=1;i<=n;i++)
if(i<=r)add(ans,C(n,i)*f[i]%MOD*(i==1));
else {
if((i-r)&1)add(ans,-C(n,i)*f[i]%MOD*C(i-2,r-1));
else add(ans,C(n,i)*f[i]%MOD*C(i-2,r-1));
}
// printf("%lld\n",(ans+MOD)%MOD);
printf("%lld\n",((ans%MOD+MOD)*ifac[n+d-1]%MOD*fac[n-1]%MOD*fac[d]%MOD+r)%MOD);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 67ms
memory: 26000kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 64ms
memory: 26032kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 69ms
memory: 26000kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 68ms
memory: 26032kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 69ms
memory: 25972kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 68ms
memory: 25956kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 65ms
memory: 26020kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 60ms
memory: 25952kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 67ms
memory: 28752kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 109ms
memory: 71048kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 87ms
memory: 71332kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 98ms
memory: 59668kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 1002ms
memory: 846252kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 66ms
memory: 31328kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 67ms
memory: 31412kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 67ms
memory: 29192kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 116ms
memory: 80268kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 105ms
memory: 80576kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 72ms
memory: 58384kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 1022ms
memory: 846420kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 1018ms
memory: 845992kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 1012ms
memory: 842684kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 68ms
memory: 26028kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 948ms
memory: 846328kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"
Extra Test:
score: 0
Extra Test Passed