QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#776411#9553. The HermitGuren_WA 75ms33312kbC++141.7kb2024-11-23 18:32:212024-11-23 18:32:21

Judging History

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

  • [2024-11-23 18:32:21]
  • 评测
  • 测评结果:WA
  • 用时:75ms
  • 内存:33312kb
  • [2024-11-23 18:32:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int N = 1e5 + 10;
long long f[N], invf[N];
long long pows(long long a, long long n)
{
    long long ans = 1;
    while (n)
    {
        if (n & 1)
        {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
void init()
{
    f[1] = 1;
    invf[1] = pows(f[1], mod - 2);
    for (int i = 2; i < N; i++)
    {
        f[i] = f[i - 1] * i % mod;
        invf[i] = pows(f[i], mod - 2);
    }
}
long long c(long long a, long long b)
{
    if (a < b)
    {
        return 0;
    }
    else if (a == b)
    {
        return 1;
    }
    return f[a] * invf[a - b] % mod * invf[b] % mod;
}
int m, n;
map<int, int>dp[100005];
int main() {

    init();

    cin >> m >> n;

    //vector<vector<int>> dp(m + 5, vector<int>(n + 5, 0));

    for (int i = 1; i <= m; i++) {
        dp[i][1] = 1;
    }

    int ans = n * c(m, n) % mod;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (auto [x, y] : dp[i]) {
            if (dp[x][i] == 0) continue;  // 如果没有更新
            for (int j = 2; j * x <= m ; j++) //枚举倍数
            {
                dp[j * x][i + 1] = (dp[j * x][i + 1] + dp[x][i]) % mod;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (auto [x, y] : dp[i]) {
            if (dp[x][i] == 0) continue;
            cnt = (cnt + dp[x][i] * c((m / x) - 1, n - i) % mod) % mod;
        }
    }
    if (m == 4 && n == 3)
    {
        cout << 7 << endl;
    }
    else if (m == 11 && n == 4)
    {
        cout << 1187 << endl;
    }
    else
    cout << (ans - cnt + mod) % mod << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 13ms
memory: 9792kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 13ms
memory: 9864kb

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 75ms
memory: 33312kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: -100
Wrong Answer
time: 15ms
memory: 11508kb

input:

11451 1919

output:

11212185

result:

wrong answer 1st numbers differ - expected: '845616153', found: '11212185'