QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#772599#9553. The Hermitsky10wTL 2ms5280kbC++171.9kb2024-11-22 20:37:562024-11-22 20:38:02

Judging History

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

  • [2024-11-22 20:38:02]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:5280kb
  • [2024-11-22 20:37:56]
  • 提交

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;
}

详细

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

output:


result: