QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#790676 | #9553. The Hermit | ykpcx# | TL | 50ms | 4632kb | C++23 | 1.2kb | 2024-11-28 14:35:03 | 2024-11-28 14:35:04 |
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4548kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4620kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 1ms
memory: 4600kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: 0
Accepted
time: 5ms
memory: 4632kb
input:
11451 1919
output:
845616153
result:
ok 1 number(s): "845616153"
Test #5:
score: 0
Accepted
time: 50ms
memory: 4628kb
input:
99998 12345
output:
936396560
result:
ok 1 number(s): "936396560"
Test #6:
score: 0
Accepted
time: 25ms
memory: 4552kb
input:
100000 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: -100
Time Limit Exceeded
input:
100000 15