結果
問題 | No.2068 Restricted Permutation |
ユーザー |
![]() |
提出日時 | 2022-09-02 23:02:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 3,166 bytes |
コンパイル時間 | 2,026 ms |
コンパイル使用メモリ | 173,384 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-16 05:40:20 |
合計ジャッジ時間 | 2,745 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>int ri() {int n;scanf("%d", &n);return n;}template<int mod> struct mod_int {static constexpr int MOD = mod;int x = 0;mod_int () = default;mod_int (int64_t x) : x(x >= 0 ? x % mod : (mod - -x % mod) % mod) {}static mod_int raw(int x) { mod_int res; res.x = x; return res; }mod_int &operator += (const mod_int &p){if ((x += p.x) >= mod) x -= mod;return *this;}mod_int &operator -= (const mod_int &p) {if ((x -= p.x) < 0) x += mod;return *this;}mod_int &operator *= (const mod_int &p) { x = (int64_t) x * p.x % mod; return *this; }mod_int &operator /= (const mod_int &p) { return (*this *= p.inv()); }mod_int &operator ^= (int64_t p) {mod_int res = 1;for (; p; p >>= 1) {if (p & 1) res *= *this;*this *= *this;}return *this = res;}mod_int operator - () const { return mod_int(-x); }mod_int operator + (const mod_int &p) const { return mod_int(*this) += p; }mod_int operator - (const mod_int &p) const { return mod_int(*this) -= p; }mod_int operator * (const mod_int &p) const { return mod_int(*this) *= p; }mod_int operator / (const mod_int &p) const { return mod_int(*this) /= p; }mod_int operator ^ (int64_t p) const { return mod_int(*this) ^= p; }bool operator == (const mod_int &p) const { return x == p.x; }bool operator != (const mod_int &p) const { return x != p.x; }explicit operator int() const { return x; }mod_int inv() const {int a = x, b = mod, u = 1, v = 0, t;while (b > 0) {t = a / b;a -= t * b;std::swap(a, b);u -= t * v;std::swap(u, v);}return mod_int(u);}friend std::ostream &operator << (std::ostream &stream, const mod_int<mod> &p) {return stream << p.x;}friend std::istream &operator >> (std::istream &stream, mod_int<mod> &a) {int64_t x;stream >> x;a = mod_int<mod>(x);return stream;}};using mint = mod_int<998244353>;template<typename mint> struct MComb {std::vector<mint> fact;std::vector<mint> inv;MComb (int n) { // O(n + log(mod))fact = std::vector<mint>(n + 1, 1);for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * mint(i);inv.resize(n + 1);inv[n] = fact[n].inv();for (int i = n; i--; ) inv[i] = inv[i + 1] * mint(i + 1);}mint ncr(int n, int r) {assert(0 <= r && r <= n && n <= (int) fact.size());return fact[n] * inv[r] * inv[n - r];}mint npr(int n, int r) {assert(0 <= r && r <= n && n <= (int) fact.size());return fact[n] * inv[n - r];}mint nhr(int n, int r) { return ncr(n + r - 1, r); }};int main() {int n = ri();int k = ri() - 1;int x = ri() - 1;MComb<mint> com(n);mint res = 0;for (int i = 0; i < n; i++) {if (i == k) {res += mint(x) * mint(n - 1 - i) * com.fact[n - 2] * com.fact[n - 1 - i];} else {// lowerint right = n - i - 1 - (i < k);res += mint(x) * (x - 1) / 2 * right * com.fact[n - 3] * com.fact[n - 1 - i];// higherres += mint(x + n - 2) * (n - 2 - x + 1) / 2 * right * com.fact[n - 3] * com.fact[n - 1 - i];// k:xif (i < k) res += mint(n - 1 - x) * com.fact[n - 2] * com.fact[n - 1 - i];}}std::cout << res << std::endl;return 0;}