QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#790651 | #9553. The Hermit | ykpcx# | TL | 50ms | 4740kb | C++23 | 1.2kb | 2024-11-28 14:26:59 | 2024-11-28 14:27:00 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
using ll = long long;
const ll M = 998244353;
const int N = 1e5 + 5;
int n, m, k;
ll fact[N];
ll qp(ll x, ll n) {
ll ret = 1;
while (n) {
if (n & 1) ret = ret * x % M;
x = x * x % M;
n >>= 1;
}
return ret;
}
ll inv(ll x) {
return qp(x, M - 2);
}
ll C(ll n, ll k) {
if (n < k) return 0;
return fact[n] * inv(fact[k] * fact[n - k] % M) % M;
}
ll f(int m, int n) {
if (m - 1 < n) return 0;
if (n == 0) {
return 0;
}
ll ret = 0;
for (int i = 2; i + n - 1 <= m; i++) {
int x = m / i - 1;
int y = m - i;
ll tot = ((C(y, n - 1) - C(x, n - 1)) % M + M) % M;
ret = (tot * n % M + ret) % M;
ret = (ret + f(x + 1, n - 1)) % M;
}
return ret;
}
void init() {
fact[0] = 1;
for (int i = 1; i < N; i++) {
fact[i] = fact[i - 1] * i % M;
}
}
void solve() {
cin >> m >> n;
printf("%lld\n", (f(m, n) + f(m, n - 1) % M));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
init();
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4608kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4608kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 0ms
memory: 4740kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: 0
Accepted
time: 5ms
memory: 4528kb
input:
11451 1919
output:
845616153
result:
ok 1 number(s): "845616153"
Test #5:
score: 0
Accepted
time: 50ms
memory: 4540kb
input:
99998 12345
output:
936396560
result:
ok 1 number(s): "936396560"
Test #6:
score: 0
Accepted
time: 22ms
memory: 4604kb
input:
100000 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: -100
Time Limit Exceeded
input:
100000 15