QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791771 | #9553. The Hermit | hhu_yjh | TL | 924ms | 24612kb | C++14 | 2.0kb | 2024-11-28 20:46:59 | 2024-11-28 20:47:04 |
Judging History
answer
#include <bits/stdc++.h>
#define dbg() cout<<"-------"
typedef long long ll;
using namespace std;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int N=2e6+10;
const int mod=998244353;
ll n,m;
ll dp[N][20];
ll fact[N];
ll qmi(ll x,ll y,ll mod){
ll res=1,t=x%mod;
while(y){
if(y&1) res=res*t%mod;
t=t*t%mod;
y>>=1;
}
return res;
}
ll c(int n,int m){
if(m>n) return 0;
return fact[n]*qmi(fact[m],mod-2,mod)%mod*qmi(fact[n-m],mod-2,mod)%mod;
//return fact[n]*qmi(fact[m]*fact[n-m]%mod,mod-2,mod)%mod;
}
void solve(){
cin>>m>>n;
fact[0]=1;for(int i=1;i<=m;i++) fact[i]=fact[i-1]*i%mod;
//cout<<c(3,0)<<'\n';
// cout<<"*****"<<'\n';
for(int i=1;i<=m;i++) dp[i][1]=1;
for(int len=1;len<=17;len++){
for(int i=1;i<=m;i++){
for(int j=2*i;j<=m;j+=i){
dp[j][len+1]+=dp[i][len];
dp[j][len+1]%=mod;
}
}
}
// cout<<dp[1][1]<<' '<<dp[1][2]<<'\n';
// cout<<"..."<<'\n';
ll ans=0;
for(int i=1;i<=m;i++){
int cnt=m/i-1;
ans+=(c(m-i,n-1)-c(cnt,n-1))*n%mod;
//cout<<i<<"..."<<ans<<'\n';
ans%=mod;
}
//cout<<ans<<'\n';
// exit(0);
//ans=0;/////////////////
for(int g=1;g<=m;g++){
for(int len=1;len<=min(18ll,n-1);len++){
for(int t=2*g;t<=m;t+=g){
int cnt=m/g-t/g;
int cnt2=m/t-1;
ans+=(c(cnt,n-len-1)-c(cnt2,n-len-1))%mod*dp[g][len]%mod*(n-len)%mod;
// if((c(cnt,n-len-1)-c(cnt2,n-len-1))*dp[g][len]%mod*(n-len)%mod){
// cout<<g<<' '<<len<<" "<<t<<'\n';
// }
ans%=mod;
}
}
// cout<<g<<"..."<<ans<<'\n';
}
cout<<((ans%mod)+mod)%mod<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
//cin>>t;
t=1;
while(t--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5572kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 174ms
memory: 24612kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: 0
Accepted
time: 82ms
memory: 7840kb
input:
11451 1919
output:
845616153
result:
ok 1 number(s): "845616153"
Test #5:
score: 0
Accepted
time: 924ms
memory: 20808kb
input:
99998 12345
output:
936396560
result:
ok 1 number(s): "936396560"
Test #6:
score: 0
Accepted
time: 105ms
memory: 20820kb
input:
100000 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: -100
Time Limit Exceeded
input:
100000 15