#503265 (C++14) No.1100 Boxes

• 問題: No.1100 Boxes
• ユーザー: heno239
• 提出日時: 2020-06-26 22:03:32
• 言語: C++14 (gcc 12.3.0 + boost 1.83.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	3 ms; 5,376 KB
testcase_18	AC	3 ms; 5,376 KB
testcase_19	AC	6 ms; 5,376 KB
testcase_20	AC	22 ms; 5,376 KB
testcase_21	AC	83 ms; 10,308 KB
testcase_22	AC	177 ms; 17,556 KB
testcase_23	AC	84 ms; 10,308 KB
testcase_24	AC	91 ms; 10,540 KB
testcase_25	AC	96 ms; 10,736 KB
testcase_26	AC	190 ms; 17,824 KB
testcase_27	AC	175 ms; 17,360 KB
testcase_28	AC	44 ms; 6,864 KB
testcase_29	AC	184 ms; 17,544 KB
testcase_30	AC	173 ms; 17,268 KB
testcase_31	AC	52 ms; 7,136 KB
testcase_32	AC	101 ms; 10,876 KB
testcase_33	AC	193 ms; 17,904 KB
testcase_34	AC	196 ms; 17,812 KB
testcase_35	AC	2 ms; 5,376 KB
testcase_36	AC	172 ms; 17,940 KB
testcase_37	AC	2 ms; 5,376 KB
testcase_38	AC	90 ms; 10,492 KB
testcase_39	AC	189 ms; 17,860 KB

ソースコード

#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;
}