結果
| 問題 | No.1321 塗るめた |
| ユーザー |
 37zigen
|
| 提出日時 | 2020-12-18 03:49:22 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,919 bytes |
| コンパイル時間 | 1,723 ms |
| コンパイル使用メモリ | 110,172 KB |
| 最終ジャッジ日時 | 2025-01-17 02:42:41 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 44 TLE * 1 |
ソースコード
#include <string>#include <iostream>#include <vector>#include <cassert>#include <random>constexpr long long p = 998244353;long long ADD(long long a, long long b) {return a + b >= p ? a + b - p : a + b;}std::vector<long long> trim(std::vector<long long> a, int n) {std::vector<long long> b(n, 0);for (int i = 0; i < std::min(n, (int) a.size()); ++i) b[i] = a[i];return b;}std::vector<long long> shift(std::vector<long long> a, int shift) {std::vector<long long> b(a.size(), 0);for (int i = 0; i < (int) a.size(); ++i) b[i] = (0 <= i - shift && i - shift < (int) a.size()) ? a[i - shift] : 0;return b;}long long pow_mod(long long a, long long n) {return n == 0 ? 1 : (pow_mod(a * a % p, n / 2) * (n % 2 == 1 ? a : 1)) % p;}long long modinv(long long a) {return pow_mod(a, p - 2);}std::vector<long long> add(std::vector<long long> a, std::vector<long long> b) {int n = std::max(a.size(), b.size());std::vector<long long> c(n);a.resize(n);b.resize(n);for (int i = 0; i < n; ++i) c[i] = ADD(a[i], b[i]);return c;}std::vector<long long> subtract(std::vector<long long> a, std::vector<long long> b) {int n = std::max(a.size(), b.size());std::vector<long long> c(n);a.resize(n);b.resize(n);for (int i = 0; i < n; ++i) c[i] = ADD(a[i], p - b[i]);return c;}void fft(std::vector<long long> &a, long long g) {int n = a.size();g = pow_mod(g, (p - 1) / n);{int i = 0;for (int j = 0; j < n; ++j) {if (i > j) std::swap(a[i], a[j]);for (int k = n / 2; k > (i ^= k); k /= 2);}}for (int len = 1; len <= n / 2; len *= 2) {long mul = pow_mod(g, n / (2 * len));for (int src = 0; src < n; src += 2 * len) {long long x = 1;for (int pos = src; pos < src + len; ++pos) {long long A = a[pos];long long B = a[pos + len] * x % p;a[pos] = ADD(A, B);a[pos + len] = ADD(A, p - B);x = x * mul % p;}}}}std::vector<long long> mul(std::vector<long long> a, std::vector<long long> b) {long long g = 3;int n = 1;while (n < (int) (a.size() + b.size() - 1)) n *= 2;a.resize(n);b.resize(n);fft(a, g);fft(b, g);long long inv_n = modinv(n);for (int i = 0; i < n; ++i) a[i] = a[i] * b[i] % p * inv_n % p;fft(a, modinv(g));return a;}std::vector<long long> mul(std::vector<long long> a, long long b) {int n = a.size();std::vector<long long> c(n);for (int i = 0; i < n; ++i) c[i] = a[i] * b % p;return c;}std::vector<long long> finv(std::vector<long long> a) {int n = a.size();std::vector<long long> b = {modinv(a[0])};for (int len = 1; len < n; len *= 2) {b = subtract(mul(b, 2), trim(mul(mul(b, b), trim(a, 2 * len)), 2 * len));}return b;}std::vector<long long> differentiate(std::vector<long long> a) {int n = a.size();for (int i = 0; i + 1 < n; ++i) a[i] = (i + 1) * a[i + 1] % p;a[n - 1] = 0;return a;}std::vector<long long> integrate(std::vector<long long> a) {for (int i = a.size() - 1; i >= 1; --i) a[i] = modinv(i) * a[i - 1] % p;a[0] = 0;return a;}std::vector<long long> log(std::vector<long long> a) {assert(a[0] == 1);return integrate(mul(differentiate(a), finv(a)));}std::vector<long long> exp(std::vector<long long> a) {assert(a[0] == 0);int n = a.size();std::vector<long long> b = {1};for (int len = 1; len < n; len *= 2) {std::vector<long long> tmp = subtract(trim(a, 2 * len), log(trim(b, 2 * len)));++tmp[0];b = trim(mul(b, tmp), 2 * len);}return b;}std::vector<long long> pow(std::vector<long long> a, int n) {assert(n >= 1);int s = 0;while (s < (int) a.size() && a[s] == 0) ++s;if (s == (int) a.size()) return a;a = shift(a, -s);long long b = modinv(a[0]);for (int i = 0; i < (int) a.size(); ++i) a[i] = b * a[i] % p;a = log(a);for (int i = 0; i < (int) a.size(); ++i) a[i] = n % p * a[i] % p;a = exp(a);b = pow_mod(modinv(b), n % (p - 1));for (int i = 0; i < (int) a.size(); ++i) a[i] = b * a[i] % p;a = shift(a, s * n);return a;}std::vector<long long> pow_exact(std::vector<long long> a, int n) {std::vector<long long> b = {1};for (int i = 0; i < n; ++i) b = trim(mul(b, a), a.size());return b;}void verify() {std::random_device seed_gen;std::mt19937_64 engine(seed_gen());for (int t = 0; t < 100000; ++t) {int n = engine() % 100 + 1;int k = engine() % 100 + 1;;std::vector<long long> a(n);for (int i = 0; i < n; ++i) a[i] = engine() % p;std::vector<long long> u = pow(a, k);std::vector<long long> v = pow_exact(a, k);for (int i = 0; i < n; ++i) {assert(u[i] == v[i]);}std::cout << "case" << t << ":passed" << std::endl;}}const int MAX = (int) 2e5;long long fac[MAX];long long ifac[MAX];long long inv[MAX];long long comb(int n, int k) {return fac[n] * ifac[n - k] % p * ifac[k] % p;}int main() {int N, M, K;std::cin >> N >> M >> K;fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = 1;for (int i = 2; i < MAX; ++i) {fac[i] = i * fac[i - 1] % p;inv[i] = p - inv[p % i] * (p / i) % p;ifac[i] = inv[i] * ifac[i - 1] % p;}std::vector<long long> f((int) 1e5 + 10);for (int i = 0; i < f.size(); ++i) f[i] = ifac[i];f[0] = 0;f = pow(f, K);long long ans = 0;for (int i = K; i <= N; ++i) {ans += comb(N, i) * comb(M, K) % p * pow_mod(M, N - i) % p * f[i] % p * fac[i] % p;ans %= p;}std::cout << ans << std::endl;}