QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#800954 | #9553. The Hermit | Pepinot | WA | 25ms | 21052kb | C++23 | 945b | 2024-12-06 17:18:24 | 2024-12-06 17:18:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int jc[100100],ij[101001];
int qpow(int a,int b){
int c=1;
for(;b;b>>=1){
if(b&1)c=1ll*a*c%mod;
a=1ll*a*a%mod;
}
return c;
}
int C(int a,int b){
if(a<b||a<0||b<0)return 0;
return 1ll*jc[a]*ij[b]%mod*ij[a-b]%mod;
}
int dp[101010][20],n,m;
signed main(){
cin>>n>>m;
jc[0]=ij[0]=1;
for(int i=1;i<=n;i++) {
jc[i]=i*jc[i-1]%mod;
ij[i]=qpow(jc[i],mod-2);
}
int ans=C(n,m)*m%mod;
for(int i=1;i<=n;i++){
dp[i][1]++;
for(int k=0;k<20;k++)
if(dp[i][k])
for(int j=i*2;j<=n;j+=i)
(dp[j][k+1]+=dp[i][k])%=mod;
for(int k=1;k<20;k++)
if(dp[i][k]) {
ans-=1ll*dp[i][k]*C(n/i-1,m-k)%mod;
}
}
cout<<(ans+mod)%mod;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5628kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 25ms
memory: 21052kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 5496kb
input:
11451 1919
output:
-152628200
result:
wrong answer 1st numbers differ - expected: '845616153', found: '-152628200'