QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#620374 | #8149. Station of Fate | cy325 | WA | 0ms | 5216kb | C++20 | 1.3kb | 2024-10-07 17:49:27 | 2024-10-07 17:49:27 |
Judging History
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'