結果
問題 | No.1100 Boxes |
ユーザー |
![]() |
提出日時 | 2020-06-26 22:03:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 196 ms / 2,000 ms |
コード長 | 3,289 bytes |
コンパイル時間 | 1,305 ms |
コンパイル使用メモリ | 119,932 KB |
実行使用メモリ | 17,940 KB |
最終ジャッジ日時 | 2024-07-04 21:11:27 |
合計ジャッジ時間 | 4,636 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include<iostream>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<utility>#include<map>#include<set>#include<bitset>#include<stack>#include<cassert>#include<random>#include<unordered_map>#include<numeric>#include<complex>using namespace std;typedef long long ll;const ll mod = 998244353;const ll INF = mod * mod;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define all(x) (x).begin(),(x).end()#define stop char nyaa;cin>>nyaa;using ld = long double;const ld eps = 0.01;const ld pi = acosl(-1.0);ll mod_pow(ll a, ll n) {ll res = 1;while (n) {if (n & 1)res = res * a%mod;a = a * a%mod; n >>= 1;}return res;}ll mod_inverse(ll a) {return mod_pow(a, mod - 2);}ll root[24], invroot[24];void init() {rep(i, 24) {int n = (1 << i);root[i] = mod_pow(3, (mod - 1) / n);invroot[i] = mod_inverse(root[i]);}}typedef vector <ll> poly;poly dft(poly f, bool inverse = false) {int n = f.size(); int i, j, k;//bit左右反転for (i = 0, j = 1; j < n - 1; j++) {for (k = n >> 1; k >(i ^= k); k >>= 1);if (i > j)swap(f[i], f[j]);}for (int j = 1; (1 << j) <= n; j++) {int m = 1 << j;ll zeta = root[j];if (inverse)zeta = invroot[j];for (i = 0; i < n; i += m) {ll powzeta = 1;for (k = i; k < i + m / 2; k++) {ll t1 = f[k], t2 = powzeta * f[k + m / 2] % mod;f[k] = t1 + t2; while (f[k] >= mod)f[k] -= mod;f[k + m / 2] = t1 - t2 + mod; while (f[k + m / 2] >= mod)f[k + m / 2] -= mod;(powzeta *= zeta) %= mod;}}}if (inverse) {ll rv = mod_inverse(n);for (i = 0; i < n; i++) {(f[i] *= rv) %= mod;}}return f;}poly multiply(poly g, poly h) {int n = 1;int pi = 0, qi = 0;rep(i, g.size())if (g[i])pi = i;rep(i, h.size())if (h[i])qi = i;int sz = pi + qi + 2;while (n < sz)n *= 2;g.resize(n); h.resize(n);/*while (g.size() < n) {g.push_back(0);}while (h.size() < n) {h.push_back(0);}*/poly gg = dft(g);poly hh = dft(h);poly ff; ff.resize(n);rep(i, n) {ff[i] = gg[i] * hh[i] % mod;}return dft(ff, true);}void solve() {int n; cin >> n;int k; cin >> k;vector<ll> facts(k + 1);facts[0] = 1;rep(i, k) {facts[i + 1] = facts[i] * (i + 1) % mod;}poly p1, p2;rep(i, k) {ll c = mod_pow((i + 1), n)*mod_pow(facts[i + 1], mod - 2) % mod;p1.push_back(c);}rep(i, k) {ll c = mod_pow(facts[i], mod - 2);if (i % 2) {c = mod - c;if (c == mod)c = 0;}p2.push_back(c);}poly p = multiply(p1, p2);vector<ll> memo;if (n != 0)memo.push_back(0);else memo.push_back(1);rep(i, k)memo.push_back(p[i]);rep(i, k + 1) {memo[i] = memo[i] * facts[i] % mod;}auto comb = [&](ll a, ll b)->ll {ll res = facts[a] * mod_pow(facts[a - b],mod-2) % mod*mod_pow(facts[b],mod-2) % mod;return res;};ll ans = 0;rep(i, k) {if (i % 2) {int x = k - i;ll csum = comb(k, i)*memo[x] % mod;ans += csum;}}cout << ans%mod << "\n";}signed main() {cin.tie(0);ios::sync_with_stdio(false);//cout << fixed << setprecision(10);//int t; cin >> t;//rep(i,t)solve();init();solve();char nyaa; cin >> nyaa;return 0;}