結果
問題 |
No.1100 Boxes
|
ユーザー |
|
提出日時 | 2023-06-02 09:21:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 28 ms / 2,000 ms |
コード長 | 1,868 bytes |
コンパイル時間 | 3,916 ms |
コンパイル使用メモリ | 259,132 KB |
最終ジャッジ日時 | 2025-02-13 17:25:08 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; struct Fast { Fast() { std::cin.tie(0); ios::sync_with_stdio(false); } } fast; #define rep(i, a, b) for (int i = (a); i < (int)(b); i++) #define rrep(i, a, b) for (int i = (int)(b)-1; i >= (a); i--) #define Yn(b) cout << ((b) ? "Yes" : "No") << "\n"; #define ll long long template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template <typename T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; } using mint = modint998244353; template <typename T> class factorial { public: factorial(int max) : n(max) { f = vector<T>(n + 1); finv = vector<T>(n + 1); f[0] = 1; for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i; finv[n] = f[n].inv(); for (int i = n; i > 0; i--) finv[i - 1] = finv[i] * i; } T fact(int k) { assert(0 <= k && k <= n); return f[k]; } T fact_inv(int k) { assert(0 <= k && k <= n); return finv[k]; } T binom(int k, int r) { assert(0 <= k && k <= n); if (r < 0 || r > k) return 0; return f[k] * finv[r] * finv[k - r]; } T inv(int k) { assert(0 < k && k <= n); return finv[k] * f[k - 1]; } private: int n; vector<T> f, finv; }; int main() { int n, k; cin >> n >> k; factorial<mint> fact(k); vector<mint> f(k + 1, 0), g(k + 1, 0); rep(i, 0, k + 1) { f[i] = i & 1 ? -fact.fact_inv(i) : fact.fact_inv(i); g[i] = mint(i).pow(n) * fact.fact_inv(i); } auto h = convolution(f, g); mint ans = 0; for (int j = 1; j <= k; j += 2) { ans += h[k - j] * fact.fact(k - j) * fact.binom(k, j); } cout << ans.val() << endl; }