QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#181028#6323. Range NEQucup-team228#AC ✓105ms35740kbC++205.3kb2023-09-16 15:16:562023-09-16 15:16:56

Judging History

你现在查看的是最新测评结果

  • [2023-09-16 15:16:56]
  • 评测
  • 测评结果:AC
  • 用时:105ms
  • 内存:35740kb
  • [2023-09-16 15:16:56]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

typedef long long ll;
typedef pair<int, int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
std::ostream& operator << (std::ostream& os, const vector<T>& a) {
    for (const T& x : a) {
        os << x << ' ';
    }
    return os;
}

template <int m>
struct mint {
    int x = 0;
    mint(int64_t a = 0) { if (a < 0) a = a % m + m; if (a >= m) a %= m; x = a; }
    friend istream& operator>>(istream& in, mint& a) { int64_t y; in >> y; a = y; return in; }
    friend ostream& operator<<(ostream& out, mint a) { return out << a.x; }
    explicit operator int() const { return x; }
    static int mod_inv(int a, int mod = m) {
        int g = mod, r = a, z = 0, y = 1;
        while (r != 0) { int q = g / r; g %= r; swap(g, r); z -= q * y; swap(z, y); }
        return z < 0 ? z + mod : z;
    }
    mint inv() const { return mod_inv(x, m); }
    friend mint binpow(mint a, int64_t b) { mint res = 1; while (b) { if (b & 1) res *= a; b >>= 1; a *= a; } return res; }
    mint pow(int64_t b) const { return binpow(*this, b); }
    mint operator-() const { return x ? m - x : 0; }
    mint& operator+=(const mint& a) { x += a.x; if (x >= m) x -= m; return *this; }
    mint& operator-=(const mint& a) { x -= a.x; if (x < 0) x += m; return *this; }
    static unsigned fast_mod(uint64_t x, unsigned mod = m) {
#if defined(_WIN32) && !defined(_WIN64)
        // Optimized mod for Codeforces 32-bit machines.
        // x must be less than 2^32 * mod for this to work, so that x / mod fits in a 32-bit integer.
        unsigned x_high = x >> 32, x_low = (unsigned) x; unsigned quot, rem;
        asm("divl %4\n" : "=a" (quot), "=d" (rem) : "d" (x_high), "a" (x_low), "r" (mod));
        return rem;
#else
        return x % mod;
#endif
    }
    mint& operator*=(const mint& a) { x = fast_mod((uint64_t) x * a.x); return *this; }
    mint& operator/=(const mint& a) { return *this *= a.inv(); }
    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }
    mint& operator++() { x = x == m - 1 ? 0 : x + 1; return *this; }
    mint& operator--() { x = x == 0 ? m - 1 : x - 1; return *this; }
    mint operator++(int) { mint a = *this; ++*this; return a; }
    mint operator--(int) { mint a = *this; --*this; return a; }
    bool operator==(const mint& a) const { return x == a.x; }
    bool operator!=(const mint& a) const { return x != a.x; }
};

const int mod = 998244353; // 985661441
const int K = 1 << 21; // be careful
const mint<mod> root = binpow(mint<mod>(3), (mod - 1) / K); 
// 3 is a primitive root modulo mod

typedef vector<mint<mod>> poly;

mint<mod> prec_w[K / 2];
mint<mod> w[K];

bool initialized = 0;
void init() {
    if (initialized) {
        return;
    }
    initialized = 1;
    prec_w[0] = 1;
    for (int i = 1; i < K / 2; i++) {
        prec_w[i] = prec_w[i - 1] * root;
    }
    for (int i = 1; i < K; i *= 2) {
        for (int j = 0; j < i; j++) {
            w[i + j] = prec_w[K / (2 * i) * j];
        }
    }
}

void fft(mint<mod>* in, mint<mod>* out, int n, int k = 1) {
    //cout << n << endl;
    if (n == 1) {
        *out = *in;
        return;
    }
    n /= 2;
    fft(in, out, n, 2 * k);
    fft(in + k, out + n, n, 2 * k);
    for (int i = 0; i < n; i++) {
        mint<mod> t = out[i + n] * w[i + n];
        out[i + n] = out[i] - t;
        out[i] += t;
    }
}

poly eval(poly& a) {
    while (__builtin_popcount(a.size()) != 1) {
        a.push_back(0);
    }
    poly res(a.size());
    fft(a.data(), res.data(), a.size());
    return res;
}

poly inter(poly a) {
    int n = a.size();
    poly res(n);
    fft(a.data(), res.data(), n);
    for (int i = 0; i < n; i++) {
        res[i] /= n;
    }
    reverse(res.begin() + 1, res.end());
    return res;
}

using Mint = mint<mod>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    int N = n * m;
    vector<Mint> fact(N + 1), rfact(N + 1);
    fact[0] = 1;
    for (int i = 1; i <= N; ++i) {
        fact[i] = i * fact[i - 1];
    }
    rfact[N] = fact[N].inv();
    for (int i = N; i > 0; --i) {
        rfact[i - 1] = rfact[i] * i;
    }

    auto C = [&](int n1, int k1) {
        return fact[n1] * rfact[k1] * rfact[n1 - k1];
    };

    init();

    int L = 1 << 20;
    vector<Mint> a(L, 0);
    vector<Mint> res(L);
    for (int i = 0; i <= m; ++i) {
        if (i & 1) {
            a[i] = mod - C(m, i) * C(m, i) * fact[i];
        } else {
            a[i] = C(m, i) * C(m, i) * fact[i];
        }
    }
    fft(a.data(), res.data(), L);
    for (int i = 0; i < L; ++i) {
        res[i] = res[i].pow(n);
    }
    vector<Mint> b(L, 0);
    fft(res.data(), b.data(), L);
    reverse(b.begin() + 1, b.end());
    for (int i = 0; i < L; ++i) {
        b[i] /= L;
    }
    
    Mint ans = 0;
    for (int k = 0; k <= N; ++k) {
        ans += b[N - k] * fact[k];
    }

    cout << ans << '\n';

    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 62ms
memory: 27692kb

input:

2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 59ms
memory: 27628kb

input:

5 1

output:

44

result:

ok 1 number(s): "44"

Test #3:

score: 0
Accepted
time: 81ms
memory: 27948kb

input:

167 91

output:

284830080

result:

ok 1 number(s): "284830080"

Test #4:

score: 0
Accepted
time: 61ms
memory: 27704kb

input:

2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 61ms
memory: 27692kb

input:

2 3

output:

36

result:

ok 1 number(s): "36"

Test #6:

score: 0
Accepted
time: 64ms
memory: 27700kb

input:

2 4

output:

576

result:

ok 1 number(s): "576"

Test #7:

score: 0
Accepted
time: 71ms
memory: 27700kb

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #8:

score: 0
Accepted
time: 69ms
memory: 27740kb

input:

3 2

output:

80

result:

ok 1 number(s): "80"

Test #9:

score: 0
Accepted
time: 69ms
memory: 27692kb

input:

3 3

output:

12096

result:

ok 1 number(s): "12096"

Test #10:

score: 0
Accepted
time: 58ms
memory: 27672kb

input:

3 4

output:

4783104

result:

ok 1 number(s): "4783104"

Test #11:

score: 0
Accepted
time: 67ms
memory: 27700kb

input:

4 1

output:

9

result:

ok 1 number(s): "9"

Test #12:

score: 0
Accepted
time: 62ms
memory: 27760kb

input:

4 2

output:

4752

result:

ok 1 number(s): "4752"

Test #13:

score: 0
Accepted
time: 70ms
memory: 27624kb

input:

4 3

output:

17927568

result:

ok 1 number(s): "17927568"

Test #14:

score: 0
Accepted
time: 62ms
memory: 27704kb

input:

4 4

output:

776703752

result:

ok 1 number(s): "776703752"

Test #15:

score: 0
Accepted
time: 64ms
memory: 27576kb

input:

5 2

output:

440192

result:

ok 1 number(s): "440192"

Test #16:

score: 0
Accepted
time: 63ms
memory: 27632kb

input:

5 3

output:

189125068

result:

ok 1 number(s): "189125068"

Test #17:

score: 0
Accepted
time: 69ms
memory: 27692kb

input:

5 4

output:

975434093

result:

ok 1 number(s): "975434093"

Test #18:

score: 0
Accepted
time: 100ms
memory: 35740kb

input:

1000 1000

output:

720037464

result:

ok 1 number(s): "720037464"

Test #19:

score: 0
Accepted
time: 71ms
memory: 27960kb

input:

72 42

output:

638177567

result:

ok 1 number(s): "638177567"

Test #20:

score: 0
Accepted
time: 73ms
memory: 27640kb

input:

15 19

output:

663050288

result:

ok 1 number(s): "663050288"

Test #21:

score: 0
Accepted
time: 72ms
memory: 27880kb

input:

68 89

output:

94365047

result:

ok 1 number(s): "94365047"

Test #22:

score: 0
Accepted
time: 73ms
memory: 27912kb

input:

92 37

output:

652605307

result:

ok 1 number(s): "652605307"

Test #23:

score: 0
Accepted
time: 71ms
memory: 27876kb

input:

61 87

output:

498277867

result:

ok 1 number(s): "498277867"

Test #24:

score: 0
Accepted
time: 71ms
memory: 27904kb

input:

81 40

output:

133095344

result:

ok 1 number(s): "133095344"

Test #25:

score: 0
Accepted
time: 65ms
memory: 27652kb

input:

7 91

output:

524164813

result:

ok 1 number(s): "524164813"

Test #26:

score: 0
Accepted
time: 78ms
memory: 27696kb

input:

31 18

output:

361233485

result:

ok 1 number(s): "361233485"

Test #27:

score: 0
Accepted
time: 76ms
memory: 28024kb

input:

74 54

output:

500686087

result:

ok 1 number(s): "500686087"

Test #28:

score: 0
Accepted
time: 71ms
memory: 27620kb

input:

32 2

output:

586504335

result:

ok 1 number(s): "586504335"

Test #29:

score: 0
Accepted
time: 88ms
memory: 31380kb

input:

656 718

output:

346764298

result:

ok 1 number(s): "346764298"

Test #30:

score: 0
Accepted
time: 82ms
memory: 29196kb

input:

254 689

output:

358078813

result:

ok 1 number(s): "358078813"

Test #31:

score: 0
Accepted
time: 83ms
memory: 31584kb

input:

713 674

output:

914437613

result:

ok 1 number(s): "914437613"

Test #32:

score: 0
Accepted
time: 78ms
memory: 28552kb

input:

136 698

output:

56687290

result:

ok 1 number(s): "56687290"

Test #33:

score: 0
Accepted
time: 85ms
memory: 29004kb

input:

369 401

output:

312325811

result:

ok 1 number(s): "312325811"

Test #34:

score: 0
Accepted
time: 78ms
memory: 28160kb

input:

280 204

output:

280012063

result:

ok 1 number(s): "280012063"

Test #35:

score: 0
Accepted
time: 87ms
memory: 29220kb

input:

904 225

output:

162909174

result:

ok 1 number(s): "162909174"

Test #36:

score: 0
Accepted
time: 95ms
memory: 33940kb

input:

855 928

output:

39885159

result:

ok 1 number(s): "39885159"

Test #37:

score: 0
Accepted
time: 91ms
memory: 29204kb

input:

503 365

output:

745115888

result:

ok 1 number(s): "745115888"

Test #38:

score: 0
Accepted
time: 82ms
memory: 33004kb

input:

646 996

output:

610925577

result:

ok 1 number(s): "610925577"

Test #39:

score: 0
Accepted
time: 99ms
memory: 35064kb

input:

990 918

output:

203469632

result:

ok 1 number(s): "203469632"

Test #40:

score: 0
Accepted
time: 94ms
memory: 34936kb

input:

961 949

output:

169566857

result:

ok 1 number(s): "169566857"

Test #41:

score: 0
Accepted
time: 95ms
memory: 34824kb

input:

946 932

output:

352423195

result:

ok 1 number(s): "352423195"

Test #42:

score: 0
Accepted
time: 92ms
memory: 34684kb

input:

903 981

output:

196309824

result:

ok 1 number(s): "196309824"

Test #43:

score: 0
Accepted
time: 89ms
memory: 34652kb

input:

916 988

output:

487208972

result:

ok 1 number(s): "487208972"

Test #44:

score: 0
Accepted
time: 105ms
memory: 35548kb

input:

982 982

output:

387421488

result:

ok 1 number(s): "387421488"

Test #45:

score: 0
Accepted
time: 91ms
memory: 34684kb

input:

955 911

output:

955637031

result:

ok 1 number(s): "955637031"

Test #46:

score: 0
Accepted
time: 91ms
memory: 34696kb

input:

906 999

output:

798469943

result:

ok 1 number(s): "798469943"

Test #47:

score: 0
Accepted
time: 92ms
memory: 35224kb

input:

982 975

output:

193506289

result:

ok 1 number(s): "193506289"

Test #48:

score: 0
Accepted
time: 94ms
memory: 34948kb

input:

921 991

output:

431202149

result:

ok 1 number(s): "431202149"