QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#139315 | #6678. Gem Island 2 | Sorting# | AC ✓ | 1554ms | 709988kb | C++ | 1.1kb | 2023-08-12 23:27:28 | 2023-08-12 23:27:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=3e7+1;
const int iu=3e7;
const ll mod=998244353;
ll n,d,r;
ll f[N],inf[N];
ll pw(ll x,ll y){
if(y==0) return 1;
if(y%2) return x*pw(x,y-1)%mod;
ll res=pw(x,y/2);
return res*res%mod;
}
ll C(ll x,ll y){
if(y>x || y<0) return 0;
return f[x]*inf[y]%mod*inf[x-y]%mod;
}
ll frog[N];//expected value of min(c1,...,ck)
ll save[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin >> n >> d >> r;
f[0]=1;
for(int i=1; i<=iu ;i++) f[i]=f[i-1]*i%mod;
inf[iu]=pw(f[iu],mod-2);
for(int i=iu; i>=1 ;i--) inf[i-1]=inf[i]*i%mod;
ll ans=d+r;
for(int j=1; j<=d ;j++) save[j]=C(n-1+d-j,n-1);
for(int i=n; i>=1 ;i--){
for(int r=1; r*i<=d ;r++){
frog[i]=frog[i]+save[r*i];
}
frog[i]%=mod;
frog[i]=frog[i]*f[d]%mod*f[n-1]%mod*inf[n+d-1]%mod;
/*cout << frog[i] << ' ';
cout << endl;*/
ll ways=frog[i]*C(n,i)%mod;
ll co=C(i-2,r-1);
if(i%2!=r%2) co=(mod-co)%mod;
ans=(ans+co*ways)%mod;
}
cout << ans << '\n';
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 157ms
memory: 472796kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 164ms
memory: 473512kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 201ms
memory: 472640kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 226ms
memory: 473580kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 133ms
memory: 472624kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 245ms
memory: 472388kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 194ms
memory: 473388kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 184ms
memory: 472984kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 211ms
memory: 473844kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 257ms
memory: 488468kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 183ms
memory: 488756kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 206ms
memory: 484700kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 1471ms
memory: 709988kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 240ms
memory: 477004kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 236ms
memory: 476804kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 234ms
memory: 474004kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 294ms
memory: 490048kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 269ms
memory: 490012kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 249ms
memory: 482524kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 1357ms
memory: 708012kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 1497ms
memory: 707948kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 1554ms
memory: 708932kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 201ms
memory: 473240kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 1495ms
memory: 707904kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"