QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#416910 | #6678. Gem Island 2 | unputdownable | AC ✓ | 778ms | 601896kb | C++17 | 2.0kb | 2024-05-22 10:48:09 | 2024-05-22 10:48:10 |
Judging History
answer
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
// #define int long long
#define i64 long long
#define pii pair <int, int>
using namespace std;
inline int read(void) {
int x=0,sgn=1; char ch=getchar();
while(ch<48||57<ch) {if(ch==45)sgn=0;ch=getchar();}
while(47<ch&&ch<58) {x=x*10+ch-48; ch=getchar();}
return sgn? x:-x;
}
void write(__int128 x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
/*
write((Ans%p+p)%p); pls
*/
const int p=998244353;
inline void Add(int&x,const int y) { (x+=y)>=p && (x-=p); }
inline int ksm(int x,int a=p-2) {
int res=1;
for(; a; a>>=1,x=1ll*x*x%p) (a&1) && (res=1ll*res*x%p);
return res;
}
i64 fac[30000007],ifc[30000007];
inline void init(const int L) { // Please make sure that L <= N
fac[0]=1;
for(int i=1; i<=L; ++i) fac[i]=fac[i-1]*i%p;
ifc[L]=ksm(fac[L]);
for(int i=L; i>=1; --i) ifc[i-1]=ifc[i]*i%p;
}
inline int C(int a,int b) { return fac[a]*ifc[b]%p*ifc[a-b]%p; }
inline int P(int x,int y) { return fac[x+y]*ifc[x]%p*ifc[y]%p; }
int n,d,r,cntp;
int isp[30000007],f[30000007],pri[3000006];
inline int calc(int k) {
if(k<=r) return k==1;
if((k-r)&1) return p-C(k-2,r-1);
return C(k-2,r-1);
}
signed main() {
// freopen("localinput","r",stdin);
// freopen("localoutput","w",stdout);
n=read(); d=read(); r=read(); isp[1]=1; init(n+d);
for(int i=2; i<=d; ++i) if(!isp[i]) {
pri[++cntp]=i;
for(int u=i; u<=d; u+=i) isp[u]=1;
}
for(int i=1; i<=d; ++i) f[i]=P(d-i,n-1);
for(int u=1; u<=cntp; ++u)
for(int i=d/pri[u]; i>=1; --i)
Add(f[i],f[i*pri[u]]);
__int128 Ans=0;
for(int i=1; i<=n; ++i) Ans+=(__int128)(1ll*C(n,i)*calc(i))*f[i];
Ans=(Ans%p*ksm(P(n-1,d))+r)%p;
write(Ans); puts("");
// fprintf(stderr,"%.4lf\n",1.0*clock()/CLOCKS_PER_SEC);
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 11752kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 2ms
memory: 11976kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 1ms
memory: 12012kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 0ms
memory: 11760kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 0ms
memory: 11752kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 0ms
memory: 11984kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 1ms
memory: 11816kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 1ms
memory: 11752kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 3ms
memory: 14096kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 22ms
memory: 42372kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 33ms
memory: 42424kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 25ms
memory: 34228kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 733ms
memory: 598500kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 2ms
memory: 15924kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 0ms
memory: 17996kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 0ms
memory: 13868kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 34ms
memory: 51040kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 31ms
memory: 52728kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 19ms
memory: 34648kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 778ms
memory: 597500kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 742ms
memory: 597176kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 737ms
memory: 599608kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 0ms
memory: 11752kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 751ms
memory: 601896kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"
Extra Test:
score: 0
Extra Test Passed