結果
問題 | No.2068 Restricted Permutation |
ユーザー |
![]() |
提出日時 | 2022-08-11 01:26:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,169 bytes |
コンパイル時間 | 3,084 ms |
コンパイル使用メモリ | 177,172 KB |
最終ジャッジ日時 | 2025-01-30 20:05:40 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 WA * 4 MLE * 4 |
ソースコード
#include <stdio.h>#include <math.h>#include <iostream>#include <iomanip>#include <vector>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <queue>#include <stack>#include <numeric>#include <algorithm>using namespace std;using ll = long long;#include <atcoder/all>using namespace atcoder;using mint = modint998244353;#define rep(i, n) for (ll i = 0; i < n; i++)#define ALL(a) (a).begin(), (a).end()int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n, k, x;cin >> n >> k >> x;vector<mint> fa(n + 1);fa[0] = 1;rep(i, n) fa[i + 1] = (i + 1) * fa[i];vector<vector<mint>> d(k, vector<mint>(x));rep(j, x) d[k - 1][j] = fa[n - k] * fa[n - k] * j + fa[n - k] * (fa[n - k] - 1) / 2;for (int i = k - 2; i >= 0; i--){d[i][0] = (n - i - 1) * (n - i) / 2 * fa[n - i - 1] * fa[n - i - 2] + (n - i - 1) * d[i + 1][0];for (int j = 1; j < x; j++)d[i][j] = ((n - i - 1) * (n - i) / 2 - j) * fa[n - i - 1] * fa[n - i - 2] + j * d[i + 1][j - 1] + (n - i - j - 1) * d[i + 1][j];}cout << d[0][x - 1].val() << endl;return 0;}