QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#772599 | #9553. The Hermit | sky10w | TL | 2ms | 5280kb | C++17 | 1.9kb | 2024-11-22 20:37:56 | 2024-11-22 20:38:02 |
Judging History
answer
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include "../../dbg.h"
#else
#define dbg(...) (__VA_ARGS__)
#endif
#define IOS_FAST ios::sync_with_stdio(false), cin.tie(0);
using namespace std;
using ll = long long;
#define int ll
constexpr int MOD = 998244353ll;
constexpr int MAXN = 1e5 + 10;
int nn[MAXN];
int rr[MAXN];
int mod(int x) { return (x % MOD + MOD) % MOD; }
int qpow(int a, int b)
{
int ans = 1ll;
int res = mod(a);
for (; b; b >>= 1ll)
{
if (b & 1ll)
{
ans *= res;
ans %= MOD;
}
res *= res;
res %= MOD;
}
return ans;
}
int getinv(int x)
{
return qpow(x, MOD - 2);
}
void pre()
{
nn[0] = 1;
for (int i = 1; i < MAXN; ++i)
{
nn[i] = (nn[i - 1] * i) % MOD;
}
rr[MAXN - 1] = getinv(nn[MAXN - 1]);
rr[0] = 1;
for (int i = MAXN - 2; i >= 1; --i)
{
rr[i] = (rr[i + 1] * (i + 1)) % MOD;
}
}
int getC(int u, int v)
{
// dbg(u, v);
if (u < v) return 0;
assert(u >= 0 && v >= 0);
return (nn[u] * rr[v]) % MOD * rr[u - v] % MOD;
}
int ans;
void dfs(int num, int time, const int m, const int n)
{
if (n <= time)
{
// cerr << num << ": " << 1 << '\n';
ans = mod(ans + 1);
return;
}
for (int i = 2; i <= m; ++i)
{
if (num * i > m) break;
const int cnt = (m / num - (num * i) / num);
const int tmp = getC(cnt, n - time - 1);
// cerr << num << ": " << tmp << '\n';
ans = mod(ans + tmp);
dfs(num * i, time + 1, m, n);
}
}
signed main()
{
pre();
// dbg(getC(3, 2), getC(6, 2));
int m, n;
cin >> m >> n;
ans = 0;
for (int i = 1; i <= m; ++i)
{
dfs(i, 1, m, n);
}
// dbg(ans, m, n);
ans = mod(getC(m, n) * n - ans);
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5280kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5216kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: -100
Time Limit Exceeded
input:
100000 99999