QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#758204 | #9553. The Hermit | light_ink_dots# | WA | 4ms | 12104kb | C++20 | 817b | 2024-11-17 16:43:46 | 2024-11-17 16:43:47 |
Judging History
answer
//Cut it out, you've already lost.
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005,mod=998244353;
int n,m,T,ans,flg;
int a[maxn],fac[maxn],nfac[maxn],inv[maxn],d[maxn];
inline int C(int a,int b){
return a<b? 0:1ll*fac[a]*nfac[b]%mod*nfac[a-b]%mod;
}
int main(){
scanf("%d%d",&m,&n);
fac[0]=fac[1]=nfac[0]=nfac[1]=inv[1]=1;
for(int i=2;i<maxn;i++){
fac[i]=1ll*fac[i-1]*i%mod;
inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;
nfac[i]=1ll*nfac[i-1]*inv[i]%mod;
}
for(int i=1;i<=m;i++)
for(int j=i;j<=m;j+=i)
d[j]++;
for(int i=1;i<=m;i++)
for(int j=0;j<=d[i]-1&&j+1<=n;j++){
// printf("i=%d %d %d %d\n",i,d[i]-1,C(d[i]-1,j),C(m/i-1,n-j-1));
ans=(ans+1ll*C(d[i]-1,j)*C(m/i-1,n-j-1))%mod;
}
ans=(1ll*C(m,n)*n-ans+mod)%mod;
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12104kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: -100
Wrong Answer
time: 4ms
memory: 11964kb
input:
11 4
output:
1185
result:
wrong answer 1st numbers differ - expected: '1187', found: '1185'