結果
問題 | 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 longtemplate <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;}