QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139314 | #6678. Gem Island 2 | Sorting# | TL | 261ms | 488480kb | C++ | 1.1kb | 2023-08-12 23:21:37 | 2023-08-12 23:21:40 |
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){
//cout << "C " << x << ' ' << y << endl;
if(y>x || y<0) return 0;
//cout << f[x]*inf[y]%mod*inf[x-y]%mod << endl;
return f[x]*inf[y]%mod*inf[x-y]%mod;
}
ll frog[N];//expected value of min(c1,...,ck)
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 i=n; i>=1 ;i--){
for(int r=1; r*i<=d ;r++){
frog[i]=frog[i]+C(n-1+d-r*i,n-1);
}
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';
}
詳細信息
Test #1:
score: 100
Accepted
time: 246ms
memory: 472860kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 246ms
memory: 473292kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 201ms
memory: 472996kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 222ms
memory: 473668kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 261ms
memory: 473692kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 246ms
memory: 472720kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 219ms
memory: 472744kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 215ms
memory: 472516kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 244ms
memory: 474560kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 199ms
memory: 488480kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 205ms
memory: 487752kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 258ms
memory: 484984kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: -100
Time Limit Exceeded
input:
14999999 15000000 14999999