結果

問題 No.1321 塗るめた
ユーザー 37zigen37zigen
提出日時 2020-12-18 03:49:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,756 ms / 2,000 ms
コード長 5,919 bytes
コンパイル時間 1,670 ms
コンパイル使用メモリ 111,696 KB
実行使用メモリ 51,180 KB
最終ジャッジ日時 2024-09-21 08:52:52
合計ジャッジ時間 86,411 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,730 ms
51,048 KB
testcase_01 AC 1,733 ms
51,048 KB
testcase_02 AC 1,733 ms
51,116 KB
testcase_03 AC 1,731 ms
51,176 KB
testcase_04 AC 1,727 ms
51,176 KB
testcase_05 AC 1,734 ms
51,044 KB
testcase_06 AC 1,732 ms
51,176 KB
testcase_07 AC 1,728 ms
51,048 KB
testcase_08 AC 1,733 ms
51,052 KB
testcase_09 AC 1,735 ms
51,172 KB
testcase_10 AC 1,740 ms
51,048 KB
testcase_11 AC 1,731 ms
51,044 KB
testcase_12 AC 1,729 ms
51,048 KB
testcase_13 AC 1,732 ms
51,044 KB
testcase_14 AC 1,737 ms
51,176 KB
testcase_15 AC 1,742 ms
51,172 KB
testcase_16 AC 1,735 ms
51,048 KB
testcase_17 AC 1,736 ms
51,048 KB
testcase_18 AC 1,747 ms
51,176 KB
testcase_19 AC 1,735 ms
51,180 KB
testcase_20 AC 1,730 ms
51,176 KB
testcase_21 AC 1,746 ms
51,176 KB
testcase_22 AC 1,739 ms
51,172 KB
testcase_23 AC 1,742 ms
51,176 KB
testcase_24 AC 1,735 ms
51,176 KB
testcase_25 AC 1,756 ms
51,048 KB
testcase_26 AC 1,746 ms
51,048 KB
testcase_27 AC 1,741 ms
51,052 KB
testcase_28 AC 1,744 ms
51,172 KB
testcase_29 AC 1,739 ms
51,176 KB
testcase_30 AC 1,751 ms
51,176 KB
testcase_31 AC 1,745 ms
51,176 KB
testcase_32 AC 1,750 ms
51,048 KB
testcase_33 AC 1,732 ms
51,176 KB
testcase_34 AC 1,746 ms
51,176 KB
testcase_35 AC 1,737 ms
51,052 KB
testcase_36 AC 1,729 ms
51,048 KB
testcase_37 AC 1,741 ms
51,048 KB
testcase_38 AC 1,740 ms
51,044 KB
testcase_39 AC 1,746 ms
51,176 KB
testcase_40 AC 1,733 ms
51,048 KB
testcase_41 AC 1,734 ms
51,176 KB
testcase_42 AC 1,733 ms
51,048 KB
testcase_43 AC 1,738 ms
51,044 KB
testcase_44 AC 1,737 ms
51,052 KB
testcase_45 AC 1,736 ms
51,176 KB
testcase_46 AC 1,734 ms
51,044 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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