QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#766920#9553. The HermitLonelyperWA 150ms27796kbC++141.8kb2024-11-20 19:17:442024-11-20 19:17:46

Judging History

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

  • [2024-11-20 19:17:46]
  • 评测
  • 测评结果:WA
  • 用时:150ms
  • 内存:27796kb
  • [2024-11-20 19:17:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
const LL mod = 998244353;
LL m, n;
LL fac[N];
//f[x][i]表示以x结尾,前面有多少比x小的数的方案数
LL f[N][30];


LL qmi(LL a, LL b){
    LL ans = 1;
    a %= mod;
    while(b){
        if(b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

LL inv(LL x){
    return qmi(x, mod - 2);
}

void init(){
    fac[0] = 1;
    for(int i = 1; i <= 100000; i ++){
        fac[i] = (fac[i - 1] * i) % mod;
        // inv[i] = qmi(fac[i], mod - 2);
    }
}

LL C(LL n, LL m){
    return (fac[n] % mod * inv(fac[m]) % mod * inv(fac[n - m]) % mod) % mod;
}

vector<int> get(int x){
    vector<int> v;
    for(int i = 1; i <= x / i; i ++){
        if(i == x) continue;
        if(x % i == 0){
            v.push_back(i);
            if(x / i != i && x / i != x){
                v.push_back(x / i);
            }
        }
    }
    return v;
}

void Lonelyper(){
    cin >> m >> n;
    LL ans = C(m, n) * n;
    
    for(int i = 1; i <= m; i ++){
        vector<int> v = get(i);
        f[i][1] = 1;
        for(int j = 2; j <= 20; j ++){
            for(auto c : v){
                f[i][j] = (f[i][j] + f[c][j - 1]) % mod;
            }
        }
        int cnt = m / i - 1;
        for(int j = 1; j <= 20; j ++){
            int d = n - j;
            if(d < 0 || d > cnt) continue;
            ans = (ans - f[i][j] * C(cnt, d) % mod + mod % mod) % mod;
        }
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    init();
    // cin >> t;
    while(t --){
        Lonelyper();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5580kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 150ms
memory: 27796kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: -100
Wrong Answer
time: 11ms
memory: 8732kb

input:

11451 1919

output:

-152628200

result:

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