結果

問題 No.1100 Boxes
ユーザー heno239
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0