QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#416910#6678. Gem Island 2unputdownableAC ✓778ms601896kbC++172.0kb2024-05-22 10:48:092024-05-22 10:48:10

Judging History

你现在查看的是最新测评结果

  • [2024-05-22 10:48:10]
  • 评测
  • 测评结果:AC
  • 用时:778ms
  • 内存:601896kb
  • [2024-05-22 10:48:09]
  • 提交

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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