QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#830117#9121. I Love Marathon Contestrotcar07#AC ✓171ms19308kbC++23832b2024-12-24 16:13:272024-12-24 16:13:44

Judging History

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

  • [2024-12-24 16:13:44]
  • 评测
  • 测评结果:AC
  • 用时:171ms
  • 内存:19308kb
  • [2024-12-24 16:13:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998244353,N=2e6+5;
int n,fac[N],inv[N];
inline int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*1ll*a%mod;
        a=a*1ll*a%mod,b>>=1;
    }
    return ans;
}
inline int C(int n,int m){return (n<m||m<0)?0:fac[n]*1ll*inv[m]%mod*inv[n-m]%mod;}
int main(){
    cin>>n;
    for(int i=fac[0]=1;i<=2*n;i++) fac[i]=fac[i-1]*1ll*i%mod;
    inv[2*n]=qpow(fac[2*n],mod-2);
    for(int i=2*n;i>=1;i--) inv[i-1]=inv[i]*1ll*i%mod;
    long long res=C(2*n-1,n-1);
    for(int i=1;i<n;){
        res=res+C(2*n-1,n+i)+2*C(2*n-2,n-1+i);
        for(int k=++i;k<=n;k+=i){
            res=res-C(2*n-2,n-k)+2*C(2*n-2,n-1-k)-C(2*n-2,n-2-k);
        }
    }
    res%=mod;if(res<0)res+=mod;
    cout<<res*2*fac[n]%mod*fac[n]%mod<<'\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5684kb

input:

1

output:

2

result:

ok "2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5684kb

input:

2

output:

40

result:

ok "40"

Test #3:

score: 0
Accepted
time: 0ms
memory: 5556kb

input:

3

output:

1656

result:

ok "1656"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5608kb

input:

4

output:

112896

result:

ok "112896"

Test #5:

score: 0
Accepted
time: 1ms
memory: 5608kb

input:

5

output:

11750400

result:

ok "11750400"

Test #6:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

6

output:

741506047

result:

ok "741506047"

Test #7:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

7

output:

663688356

result:

ok "663688356"

Test #8:

score: 0
Accepted
time: 1ms
memory: 5692kb

input:

8

output:

564862407

result:

ok "564862407"

Test #9:

score: 0
Accepted
time: 1ms
memory: 5752kb

input:

9

output:

161774290

result:

ok "161774290"

Test #10:

score: 0
Accepted
time: 1ms
memory: 5672kb

input:

10

output:

652045233

result:

ok "652045233"

Test #11:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

11

output:

748014862

result:

ok "748014862"

Test #12:

score: 0
Accepted
time: 1ms
memory: 5748kb

input:

12

output:

304641307

result:

ok "304641307"

Test #13:

score: 0
Accepted
time: 1ms
memory: 5740kb

input:

13

output:

729875009

result:

ok "729875009"

Test #14:

score: 0
Accepted
time: 0ms
memory: 5612kb

input:

14

output:

711836922

result:

ok "711836922"

Test #15:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

15

output:

920550523

result:

ok "920550523"

Test #16:

score: 0
Accepted
time: 2ms
memory: 7864kb

input:

17408

output:

632438437

result:

ok "632438437"

Test #17:

score: 0
Accepted
time: 5ms
memory: 6040kb

input:

46789

output:

458137544

result:

ok "458137544"

Test #18:

score: 0
Accepted
time: 3ms
memory: 5772kb

input:

22610

output:

356200349

result:

ok "356200349"

Test #19:

score: 0
Accepted
time: 0ms
memory: 5824kb

input:

33916

output:

52946419

result:

ok "52946419"

Test #20:

score: 0
Accepted
time: 4ms
memory: 5904kb

input:

37395

output:

66208794

result:

ok "66208794"

Test #21:

score: 0
Accepted
time: 92ms
memory: 16152kb

input:

564256

output:

145325890

result:

ok "145325890"

Test #22:

score: 0
Accepted
time: 143ms
memory: 17840kb

input:

834557

output:

942727699

result:

ok "942727699"

Test #23:

score: 0
Accepted
time: 117ms
memory: 17752kb

input:

700474

output:

110750834

result:

ok "110750834"

Test #24:

score: 0
Accepted
time: 87ms
memory: 17120kb

input:

530345

output:

407205453

result:

ok "407205453"

Test #25:

score: 0
Accepted
time: 161ms
memory: 19188kb

input:

942062

output:

849740307

result:

ok "849740307"

Test #26:

score: 0
Accepted
time: 103ms
memory: 17868kb

input:

629156

output:

521070781

result:

ok "521070781"

Test #27:

score: 0
Accepted
time: 145ms
memory: 18864kb

input:

861230

output:

52253753

result:

ok "52253753"

Test #28:

score: 0
Accepted
time: 103ms
memory: 16848kb

input:

643760

output:

896717464

result:

ok "896717464"

Test #29:

score: 0
Accepted
time: 145ms
memory: 19176kb

input:

877036

output:

148107554

result:

ok "148107554"

Test #30:

score: 0
Accepted
time: 111ms
memory: 15124kb

input:

672739

output:

384285823

result:

ok "384285823"

Test #31:

score: 0
Accepted
time: 163ms
memory: 19248kb

input:

999991

output:

11040806

result:

ok "11040806"

Test #32:

score: 0
Accepted
time: 171ms
memory: 19248kb

input:

999992

output:

10247994

result:

ok "10247994"

Test #33:

score: 0
Accepted
time: 171ms
memory: 19248kb

input:

999993

output:

288885449

result:

ok "288885449"

Test #34:

score: 0
Accepted
time: 170ms
memory: 19128kb

input:

999994

output:

488915584

result:

ok "488915584"

Test #35:

score: 0
Accepted
time: 168ms
memory: 19188kb

input:

999995

output:

913096398

result:

ok "913096398"

Test #36:

score: 0
Accepted
time: 167ms
memory: 19248kb

input:

999996

output:

125855903

result:

ok "125855903"

Test #37:

score: 0
Accepted
time: 168ms
memory: 19248kb

input:

999997

output:

616335312

result:

ok "616335312"

Test #38:

score: 0
Accepted
time: 167ms
memory: 19152kb

input:

999998

output:

381708275

result:

ok "381708275"

Test #39:

score: 0
Accepted
time: 166ms
memory: 19308kb

input:

999999

output:

513037643

result:

ok "513037643"

Test #40:

score: 0
Accepted
time: 167ms
memory: 19168kb

input:

1000000

output:

252793281

result:

ok "252793281"

Extra Test:

score: 0
Extra Test Passed