QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#790676#9553. The Hermitykpcx#TL 50ms4632kbC++231.2kb2024-11-28 14:35:032024-11-28 14:35:04

Judging History

你现在查看的是最新测评结果

  • [2024-11-28 14:35:04]
  • 评测
  • 测评结果:TL
  • 用时:50ms
  • 内存:4632kb
  • [2024-11-28 14:35:03]
  • 提交

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: 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

output:


result: