QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#794360#9553. The HermitKafuuChinocpp#WA 12ms10224kbC++141.4kb2024-11-30 13:52:032024-11-30 13:52:09

Judging History

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

  • [2024-11-30 13:52:09]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:10224kb
  • [2024-11-30 13:52:03]
  • 提交

answer

#include <cstdio>
#include <algorithm>

using namespace std;

const int max1 = 1e5;
const int mod = 998244353;

int m, n;
int fac[max1 + 5], ifac[max1 + 5], ans;

int f[max1 + 5][20];

int C ( int n, int m )
{
    if ( n < 0 || m < 0 || n < m )
        return 0;
    return 1LL * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}

int main ()
{
    scanf("%d%d", &m, &n);

    fac[0] = 1;
    for ( int i = 1; i <= m; i ++ )
        fac[i] = 1LL * fac[i - 1] * i % mod;
    ifac[0] = ifac[1] = 1;
    for ( int i = 2; i <= m; i ++ )
        ifac[i] = 1LL * (mod - mod / i) * ifac[mod % i] % mod;
    for ( int i = 1; i <= m; i ++ )
        ifac[i] = 1LL * ifac[i - 1] * ifac[i] % mod;
    
    ans = 1LL * C(m, n) * n % mod;

    for ( int i = 1; i <= m; i ++ )
    {
        f[i][1] = 1;
        for ( int j = 1; j < 20; j ++ )
        {
            if ( f[i][j] )
            {
                for ( int k = 2; k * i <= m; k ++ )
                {
                    f[k * i][j + 1] = (f[k * i][j + 1] + f[i][j]) % mod;
                }
            }
        }
    }

    for ( int i = 1; i <= m; i ++ )
    {
        int cnt = m / i;

        for ( int k = 0; k <= min(cnt - 1, n - 1); k ++ )
            if ( n - k < 20 )
                ans = (ans - 1LL * C(cnt - 1, k) * f[i][n - k] + mod) % mod;
    }

    printf("%d\n", ans);

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 1620kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 12ms
memory: 10168kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: 0
Accepted
time: 0ms
memory: 4592kb

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

score: -100
Wrong Answer
time: 10ms
memory: 10224kb

input:

99998 12345

output:

-61847793

result:

wrong answer 1st numbers differ - expected: '936396560', found: '-61847793'