QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#766538 | #9553. The Hermit | laonongmin | WA | 26ms | 8164kb | C++20 | 1.5kb | 2024-11-20 17:39:54 | 2024-11-20 17:39:54 |
Judging History
answer
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int N = 200005;
const int P = 998244353;
int m,n;
int d[N],g[N];
ll fac[N],ifac[N];
ll qpow(ll x,int b)
{
ll res = 1;
while(b)
{
if(b&1) res = res*x % P;
b>>=1;
x = x*x % P;
}
return res;
}
ll inv(ll x) {return qpow(x,P-2);}
ll C(ll x,ll y){return fac[x]*ifac[x-y]%P*ifac[y]%P;}
int cnt=0;
ll b[N];
void dfs(int now)
{
if(now>0 && m<b[now]*(1<<min(20,n-now))) return;
if(now==n) {++cnt; return;}
for(int i=2;i<=m;++i)
{
if(b[now]*i > m) break;
b[now+1] = b[now]*i;
dfs(now+1);
}
}
void solve()
{
cin>>m>>n;
ll ans = (C(m,n)*n) % P;
// cout<<C(m,n)<<'\n';
for(int i=1;i<=m;++i)
{
for(int j=i+i;j<=m;j+=i)
{
++d[j]; ++g[i];
}
}
for(int i=1;i<=m;++i)
{
for(int j=1;j<=min(g[i],n-1);++j)
{
int k = n-1-j;
if(k>d[i]) continue; //左k右j
ans = (ans+P-(C(d[i],k)*C(g[i],j))%P) % P;
}
}
b[0]=1;
dfs(0);
b[1]=1;
dfs(1);
// cout<<cnt<<'\n';
ans = (ans+P-cnt) % P;
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
// cin>>T;
fac[0]=ifac[0]=1;
for(int i=1;i<N;++i)
{
fac[i]=i*fac[i-1]%P;
ifac[i]=inv(i)*ifac[i-1]%P;
}
while(T--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 20ms
memory: 7692kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 20ms
memory: 7752kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 26ms
memory: 7916kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: 0
Accepted
time: 24ms
memory: 7920kb
input:
11451 1919
output:
845616153
result:
ok 1 number(s): "845616153"
Test #5:
score: -100
Wrong Answer
time: 26ms
memory: 8164kb
input:
99998 12345
output:
195569988
result:
wrong answer 1st numbers differ - expected: '936396560', found: '195569988'