結果
問題 | No.1100 Boxes |
ユーザー | heno239 |
提出日時 | 2020-06-26 22:03:32 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 198 ms / 2,000 ms |
コード長 | 3,289 bytes |
コンパイル時間 | 1,210 ms |
コンパイル使用メモリ | 118,768 KB |
実行使用メモリ | 18,004 KB |
最終ジャッジ日時 | 2023-09-18 04:39:08 |
合計ジャッジ時間 | 4,985 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 1 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 1 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,376 KB |
testcase_15 | AC | 2 ms
4,380 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 3 ms
4,376 KB |
testcase_18 | AC | 3 ms
4,376 KB |
testcase_19 | AC | 6 ms
4,376 KB |
testcase_20 | AC | 21 ms
4,952 KB |
testcase_21 | AC | 85 ms
10,188 KB |
testcase_22 | AC | 180 ms
17,368 KB |
testcase_23 | AC | 86 ms
10,140 KB |
testcase_24 | AC | 93 ms
10,672 KB |
testcase_25 | AC | 98 ms
10,680 KB |
testcase_26 | AC | 193 ms
17,768 KB |
testcase_27 | AC | 181 ms
17,284 KB |
testcase_28 | AC | 44 ms
6,740 KB |
testcase_29 | AC | 186 ms
17,488 KB |
testcase_30 | AC | 176 ms
17,204 KB |
testcase_31 | AC | 52 ms
7,000 KB |
testcase_32 | AC | 104 ms
10,920 KB |
testcase_33 | AC | 198 ms
17,912 KB |
testcase_34 | AC | 198 ms
18,000 KB |
testcase_35 | AC | 1 ms
4,380 KB |
testcase_36 | AC | 173 ms
18,004 KB |
testcase_37 | AC | 1 ms
4,380 KB |
testcase_38 | AC | 92 ms
10,440 KB |
testcase_39 | AC | 195 ms
17,924 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; }