結果
問題 | No.1100 Boxes |
ユーザー |
![]() |
提出日時 | 2020-06-26 22:34:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 184 ms / 2,000 ms |
コード長 | 1,167 bytes |
コンパイル時間 | 521 ms |
コンパイル使用メモリ | 66,784 KB |
実行使用メモリ | 8,392 KB |
最終ジャッジ日時 | 2024-07-04 22:18:52 |
合計ジャッジ時間 | 6,596 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include <iostream>using namespace std;long long modpow(long long a, long long b, long long m) {long long p = 1, q = a;for (int i = 0; i < 32; i++) {if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }q *= q; q %= m;}return p;}long long Div(long long a, long long b, long long m) {return (a * modpow(b, m - 2, m)) % m;}long long mod = 998244353;long long N, K, power[1 << 18];long long fact[1 << 18], inv[1 << 18];void init() {fact[0] = 1; power[0] = 1;for (int i = 1; i <= 100000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;for (int i = 0; i <= 100000; i++) inv[i] = Div(1, fact[i], mod);for (int i = 1; i <= 100000; i++) power[i] = (2LL * power[i - 1]) % mod;}long long ncr(int n, int r) {if (n < r || r < 0) return 0;return (fact[n] * inv[r] % mod) * inv[n - r] % mod;}int main() {init(); cin >> N >> K;long long ret = 0;for (int i = K - 1; i >= 1; i--) {long long a1 = power[(K - 1) - i]; if (((K - 1) - i) % 2 == 1) a1 *= -1LL;long long a2 = ncr(K, i);long long a3 = modpow(i, N, mod);ret += (1LL * a1 * a2 % mod) * a3 % mod;ret = (ret + mod * mod) % mod;}cout << ret << endl;return 0;}