QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#180505 | #6678. Gem Island 2 | ucup-team870 | AC ✓ | 764ms | 706416kb | C++17 | 1.6kb | 2023-09-15 21:59:10 | 2024-04-23 17:46:22 |
Judging History
answer
//之前的方案数定义不好用了,没法优化(反演)
//
#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define Rep(i,j,k) for(int i=j;i<k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define P pair<int,int>
#define ll long long
#define vi vector<int>
#define vl vector<ll>
const int mod=998244353,N=3e7+7;
ll fac[N],inv[N];
ll C(int i,int j){
if(i<j)return 0;
return fac[i]*inv[j]%mod*inv[i-j]%mod;
}
ll qp(ll x,ll y){
ll res=1;
while(y){
if(y&1)res=res*x%mod;
x=1ll*x*x%mod; y>>=1;
}
return res;
}
void add(ll &x,ll y){
x+=y;if(x>=mod)x-=mod;
}
signed main(){
IOS
int n,d,r;cin>>n>>d>>r;
const int M=3e7;
fac[0]=1; rep(i,1,M)fac[i]=i*fac[i-1]%mod;
inv[M]=qp(fac[M],mod-2); per(i,M,1)inv[i-1]=inv[i]*i%mod;
// cout<<inv[0];return 0;
vl h(max(n,d)+1);
vi pri(d+1),notpri(d+1); int cnt=0;
rep(i,2,d){
if(!notpri[i])pri[++cnt]=i;
for(int j=1;j<=cnt && pri[j]*i<=d;++j){
notpri[pri[j]*i]=1;
if(i%pri[j]==0)break;
}
}
rep(i,1,d)h[i]=C(d-i+n-1,n-1);
per(i,cnt,1){ //狄利克雷后缀和
for(int j=d/pri[i];j;--j)add(h[j],h[j*pri[i]]); //后缀和倒着做,前缀和正着做
}
ll ans=0;
rep(k,1,n){
ll hv=h[k]*C(n,k)%mod,s;
if(k==1)s=-1;
else{
s=C(k-2,r-1); if(r&1)s=-s;
}
if(k&1)s=-s;
add(ans,hv*(s+mod)%mod);
}
cout<<(ans*fac[d]%mod*fac[n-1]%mod*qp(fac[n+d-1],mod-2)%mod+r)%mod;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 242ms
memory: 472312kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 249ms
memory: 472256kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 235ms
memory: 472312kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 251ms
memory: 472304kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 254ms
memory: 472368kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 234ms
memory: 472572kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 239ms
memory: 472376kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 242ms
memory: 472376kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 256ms
memory: 472788kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 259ms
memory: 486920kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 251ms
memory: 486828kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 254ms
memory: 483084kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 695ms
memory: 706112kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 252ms
memory: 473464kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 252ms
memory: 473460kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 264ms
memory: 473428kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 258ms
memory: 487548kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 250ms
memory: 487516kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 241ms
memory: 487536kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 764ms
memory: 706288kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 744ms
memory: 706156kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 737ms
memory: 706416kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 234ms
memory: 472308kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 716ms
memory: 706276kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"
Extra Test:
score: 0
Extra Test Passed