QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#198644 | #6736. Alice and Bob | JJBOOM | RE | 0ms | 0kb | C++14 | 945b | 2023-10-03 15:58:23 | 2023-10-03 15:58:24 |
answer
#include <bits/stdc++.h>
using namespace std;
const int mo = 998244353;
const int maxn = 1e7+9;
long long fac[maxn];
long long invfac[maxn];
long long power(int a, int b) {
long long ans = 1;
for (; b; b >>= 1, a = 1LL * a * a % mo) {
if (b & 1) {
ans *= a;
ans %= mo;
}
}
return ans;
}
int ppre(){
fac[0] = 1;
for(int i = 1; i < maxn; ++ i){
fac[i] = 1LL * fac[i-1] * i;
fac[i] %= mo;
}
invfac[maxn - 1] = power(fac[maxn - 1], mo - 2);
for (int i = maxn - 1; i; i--) {
invfac[i - 1] = 1LL * invfac[i] * i % mo;
}
// cout << invfac[2] << "\n";
assert(1LL * fac[2] * invfac[2] % mo == 1);
}
int main(){
ppre();
int n;
cin >> n;
long long ans = 0;
for(int i = 1; n - 2 * i + 1 >= 0; ++ i){
ans = (ans + 1LL * fac[n - i] * invfac[i - 1] % mo * invfac[n - 2 * i + 1] % mo * fac[i - 1] % mo * fac[n - i] % mo) % mo;
}
cout << ans << "\n";
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
1