QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#830117 | #9121. I Love Marathon Contest | rotcar07# | AC ✓ | 171ms | 19308kb | C++23 | 832b | 2024-12-24 16:13:27 | 2024-12-24 16:13:44 |
Judging History
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';
}
Details
Tip: Click on the bar to expand more detailed information
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