QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#620374#8149. Station of Fatecy325WA 0ms5216kbC++201.3kb2024-10-07 17:49:272024-10-07 17:49:27

Judging History

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

  • [2024-10-07 17:49:27]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5216kb
  • [2024-10-07 17:49:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 998244353;
const int MAXN = 100005;
ll fact[MAXN], invFact[MAXN];

// 快速幂计算 a^b % mod
ll power(ll a, ll b, ll mod) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

// 预处理阶乘和阶乘的逆元
void precomputeFactorials(int n, ll mod) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % mod;
    }
    invFact[n] = power(fact[n], mod - 2, mod);  // 使用费马小定理计算逆元
    for (int i = n - 1; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % mod;
    }
}

// 计算组合数 C(n, k) % mod
ll C(ll n, ll k, ll mod) {
    if (k > n || k < 0) return 0;
    return fact[n] * invFact[k] % mod * invFact[n - k] % mod;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    precomputeFactorials(MAXN - 1, mod); // 预处理阶乘和逆元

    ll t;
    cin >> t;
    while (t--) {
        ll n, m;
        cin >> n >> m;
        if (m > n) {
            cout << 0 << endl;
        } else {
            ll result = C(n - 1, m - 1, mod);
            cout << result << endl;
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 5216kb

input:

2
3 2
6 3

output:

2
10

result:

wrong answer 1st lines differ - expected: '12', found: '2'