QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#873841#9553. The Hermit1903331632WA 8ms19212kbC++231.6kb2025-01-27 00:59:392025-01-27 00:59:40

Judging History

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

  • [2025-01-27 00:59:40]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:19212kb
  • [2025-01-27 00:59:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
#define pii pair<int, int>
#define lowbit(x) (x & (-x))
const int mod = 998244353;
int fact[N];
int infact[N];
int qmi(int a, int b)
{
    a %= mod;
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init()
{
    fact[0] = 1;
    for (int i = 1; i < N; i++)
        fact[i] = fact[i - 1] * i % mod;
    infact[N - 1] = qmi(fact[N - 1], mod - 2);
    for (int i = N - 2; i >= 1; i--)
        infact[i] = infact[i + 1] * (i + 1) % mod;
}
int C(int n, int m)
{
    if (m < 0 || m > n)
        return 0;
    return fact[n] * infact[n - m] % mod * infact[m] % mod;
}
void solve()
{
    int n, m;
    cin >> m >> n;
    unordered_map<int, unordered_map<int, int>> f;
    for (int i = 1; i <= m; i++)
    {
        f[1][i] = 1;
    }
    int res = n * C(m, n) % mod;
    for (int i = 1; i <= n; i++)
    {
        for (auto &[x, y] : f[i])
        {
            res = res - f[i][x] * C(m / x - 1, n - i) % mod;
            res %= mod;
            if (res < 0)
                res += mod;
            // f[i][x] = y;
            for (int j = 2; j * x <= m && i + 1 <= n; j++)
            {
                (f[i + 1][j * x] += f[i][x]) %= mod;
            }
        }
    }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    init();
    // cin >> t;
    while (t--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 19212kb

input:

4 3

output:

9

result:

wrong answer 1st numbers differ - expected: '7', found: '9'