QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#406247 | #6736. Alice and Bob | gugg | TL | 0ms | 0kb | C++20 | 2.7kb | 2024-05-06 23:15:56 | 2024-05-06 23:15:58 |
answer
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <cmath>
#include <bitset>
#include <cassert>
#include <numeric>
using namespace std;
typedef long long ll;
constexpr int P = 998244353;
// assume -P <= x < 2P
ll norm(ll x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, int b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
ll x;
Z(ll x = 0) : x(norm(x% P)) {}
ll val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Z& operator*=(const Z& rhs) {
x = x * rhs.x % P;
return *this;
}
Z& operator+=(const Z& rhs) {
x = norm(x + rhs.x);
return *this;
}
Z& operator-=(const Z& rhs) {
x = norm(x - rhs.x);
return *this;
}
Z& operator/=(const Z& rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z& lhs, const Z& rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z& lhs, const Z& rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z& lhs, const Z& rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z& lhs, const Z& rhs) {
Z res = lhs;
res /= rhs;
return res;
}
friend std::istream& operator>>(std::istream& is, Z& a) {
ll v;
is >> v;
a = Z(v);
return is;
}
friend std::ostream& operator<<(std::ostream& os, const Z& a) {
return os << a.val();
}
};
const int N = 10000010;
Z fact[N], infact[N];
void init()
{
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
fact[i] = fact[i - 1] * i;
infact[i] = infact[i - 1] / i;
}
}
Z A(int a, int b)
{
return fact[a] * infact[a - b];
}
void solve()
{
int n;
cin >> n;
Z ans = 0;
for (int i = 1; i <= n; i ++)
{
if (n - i < i - 1) break;
ans += A(n - i, i - 1) * fact[n - i];
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int tt = 1;
// cin >> tt;
while (tt --)
{
solve();
}
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
1