QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#779660#9553. The HermitfruianWA 24ms3800kbC++142.2kb2024-11-24 20:53:382024-11-24 20:53:39

Judging History

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

  • [2024-11-24 20:53:39]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:3800kb
  • [2024-11-24 20:53:38]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using namespace std;

i64 p = 998244353;

i64 powmod(i64 a, i64 b) {
    i64 res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

i64 C(i64 a, i64 b){
    i64 res = 1;
    for(int i = b; i>b-a;i--){
        res *= i;
        res %= p;
    }
    for(int i = 1;i<=a;i++){
        res *= powmod(i, p-2);
        res %= p;
    }
    return res;
}

void solve() {
    int m, n;
    cin>>m>>n;
    i64 res = 0;
    i64 hc = 1;
    for(int i = m-n+1; i<=m-1;i++){
        hc *= i;
        hc %= p;
    }
    i64 k = 1;
    for(int i = 1;i<=n-1;i++){
        k *= i;
        k %= p;
    }
    hc = hc*powmod(k, p-2)%p;
    // cout<<hc<<endl;

    for(int i = 1;i<=m-n+1;i++){
        // cout<<m-i<<" "<<m-i-n+1<<" "<<hc<<endl;
        res += hc;
        hc = hc*(m-i-n+1)%p;
        hc = hc*powmod(m-i, p-2)%p;
    }

    res *= n;
    // cout<<res<<endl;

    vector<int>dp(m+1, 2);
    dp[1] = 1;
    for(int i = 2;i<=m;i++){
        for(int j = 2;;j++){
            if(i*j>m)break;
            dp[i*j] = max(dp[i]+1, dp[i*j]);
        }
    }

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

    for(int i = 1;i<=m-n+1;i++){
        int bs = (m-i)/i;
        
        int ok = 0;
        // cout<<i<<" "<<dp[i]<<" "<<bs<<" "<<endl;
        int ans = 0;
        if(bs == 0)break;
        for(int j = 1;j<=dp[i];j++){
            int a = n-j;
            if(a > bs)continue;
            if(ans == 0){
                ans = C(a, bs);
            } else {
                ans = ans * (a+1) % p;
                ans = ans * powmod(bs-a, p-2) % p;
            }
            // cout<<a<<" "<<ans<<" "<<endl;
            if(j==n-1){
                ans *= 2;
                res -= ans;
                break;
            }
            res -= ans;
        }
        // cout<<res<<endl;
        // cout<<endl;
    }
    // cout<<endl;
    cout<<(res+p)%p<<endl;

}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    // std::cin >> t;
    
    while (t--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 24ms
memory: 3800kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: -100
Wrong Answer
time: 5ms
memory: 3644kb

input:

11451 1919

output:

807161692

result:

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