結果
| 問題 |
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;
}