QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#97470#6323. Range NEQXingonAC ✓147ms108528kbC++208.9kb2023-04-16 21:22:172023-04-16 21:22:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-16 21:22:19]
  • 评测
  • 测评结果:AC
  • 用时:147ms
  • 内存:108528kb
  • [2023-04-16 21:22:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fp(i, a, b) for (int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = (a), i##_ = (b) - 1; i > i##_; --i)
const int N = 1e6 + 100, P = 998244353;
using ll = int64_t;
using Poly = vector<int>;
using MultiPoly = vector<Poly>;

//快读
template <typename T>void read(T& x){
    x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    x *= f;
}
//二次剩余
/*---------------------------------------------------------------------------*/
class Cipolla {
    int P, I2{};
    using pll = pair<ll, ll>;
#define X first
#define Y second
    ll mul(ll a, ll b) const { return a * b % P; }
    pll mul(pll a, pll b) const { return { (a.X * b.X + I2 * a.Y % P * b.Y) % P, (a.X * b.Y + a.Y * b.X) % P }; }
    template<class T> T POW(T a, int b, T x) { for (; b; b >>= 1, a = mul(a, a)) if (b & 1) x = mul(x, a); return x; }
public:
    Cipolla(int p = 0) : P(p) {}
    pair<int, int> sqrt(int n) {
        int a = rand(), x;
        if (!(n %= P)) return { 0, 0 };
        if (POW(n, (P - 1) >> 1, 1ll) == P - 1) return { -1, -1 };
        while (POW(I2 = ((ll)a * a - n + P) % P, (P - 1) >> 1, 1ll) == 1) a = rand();
        x = (int)POW(pll{ a, 1 }, (P + 1) >> 1, { 1, 0 }).X;
        if (2 * x > P) x = P - x;
        return { x, P - x };
    }
#undef X
#undef Y
};
/*---------------------------------------------------------------------------*/
#define MUL(a, b) (ll(a) * (b) % P)
#define ADD(a, b) (((a) += (b)) >= P ? (a) -= P : 0) // (a += b) %= P
#define SUB(a, b) (((a) -= (b)) < 0 ? (a) += P: 0)  // ((a -= b) += P) %= P

//预处理L以内的逆元(0 ~ L-1)
Poly getInv(int L) { Poly inv(L); inv[1] = 1; fp(i, 2, L - 1) inv[i] = MUL((P - P / i), inv[P % i]); return inv; }
auto inv = getInv(N);

//快速幂
int qpow(ll a, int b = P - 2, ll x = 1) { for (; b; b >>= 1, a = a * a % P) if (b & 1) x = x * a % P; return x; }
/*---------------------------------------------------------------------------*/
namespace NTT {
    const int g = 3;
    Poly Omega(int L) {
        int wn = qpow(g, P / L);
        Poly w(L); w[L >> 1] = 1;
        fp(i, L / 2 + 1, L - 1) w[i] = MUL(w[i - 1], wn);
        fd(i, L / 2 - 1, 1) w[i] = w[i << 1];
        return w;
    }
    auto W = Omega(1 << 23); // 注意这边的size,如果大于3e5,改成23;
    void DIF(int* a, int n) {
        for (int k = n >> 1; k; k >>= 1)
            for (int i = 0, y; i < n; i += k << 1)
                for (int j = 0; j < k; ++j)
                    y = a[i + j + k], a[i + j + k] = MUL(a[i + j] - y + P, W[k + j]), ADD(a[i + j], y);
    }
    void IDIT(int* a, int n) {
        for (int k = 1; k < n; k <<= 1)
            for (int i = 0, x, y; i < n; i += k << 1)
                for (int j = 0; j < k; ++j)
                    x = a[i + j], y = MUL(a[i + j + k], W[k + j]),
                            a[i + j + k] = x - y < 0 ? x - y + P : x - y, ADD(a[i + j], y);
        int Inv = P - (P - 1) / n;
        fp(i, 0, n - 1) a[i] = MUL(a[i], Inv);
        reverse(a + 1, a + n);
    }
}

namespace Polynomial {
    // size确定以及NTT乘法
    int norm(int n) { return 1 << ((int)log2(n - 1) + 1); }
    void norm(Poly& a) { if (!a.empty()) a.resize(norm(a.size()), 0); else a = { 0 }; }
    void DFT(Poly& a) { NTT::DIF(a.data(), a.size()); }
    void IDFT(Poly& a) { NTT::IDIT(a.data(), a.size()); }
    Poly& dot(Poly& a, Poly& b) { fp(i, 0, a.size() - 1) a[i] = MUL(a[i], b[i]); return a; }

    // 和整数的乘除运算
    Poly& operator*=(Poly& a, int b) { for (auto& x : a) x = MUL(x, b); return a; }
    Poly operator*(Poly a, int b) { return a *= b; }
    Poly operator*(int a, Poly b) { return b * a; }
    Poly& operator/=(Poly& a, int b) { return a *= qpow(b); }
    Poly operator/(Poly a, int b) { return a /= b; }

    // 多项式之间的加减运算
    Poly& operator+=(Poly& a, Poly b) {
        a.resize(max(a.size(), b.size()));
        fp(i, 0, b.size() - 1) ADD(a[i], b[i]);
        return a;
    }
    Poly operator+(Poly a, Poly b) { return a += b; }
    Poly& operator-=(Poly& a, Poly b) {
        a.resize(max(a.size(), b.size()));
        fp(i, 0, b.size() - 1) SUB(a[i], b[i]);
        return a;
    }
    Poly operator-(Poly a, Poly b) { return a -= b; }

    // 多项式乘法
    Poly operator*(Poly a, Poly b) {
        int n = a.size() + b.size() - 1, L = norm(n);
        if (a.size() <= 30 || b.size() <= 30) {
            Poly c(n);
            fp(i, 0, a.size() - 1) fp(j, 0, b.size() - 1)
                    c[i + j] = (c[i + j] + (ll)a[i] * b[j]) % P;
            return c;
        }
        a.resize(L), b.resize(L);
        DFT(a), DFT(b), dot(a, b), IDFT(a);
        return a.resize(n), a;
    }

    // 多项式逆元
    Poly Inv2k(Poly a) { // |a| = 2 ^ k
        int n = a.size(), m = n >> 1;
        if (n == 1) return { qpow(a[0]) };
        Poly b = Inv2k(Poly(a.begin(), a.begin() + m)), c = b;
        b.resize(n), DFT(a), DFT(b), dot(a, b), IDFT(a);
        fp(i, 0, n - 1) a[i] = i < m ? 0 : P - a[i];
        DFT(a), dot(a, b), IDFT(a);
        return move(c.begin(), c.end(), a.begin()), a;
    }
    Poly Inv(Poly a) {
        int n = a.size();
        norm(a), a = Inv2k(a);
        return a.resize(n), a;
    }

    // 多项式除法/取模
    Poly operator/(Poly a, Poly b) {
        int k = a.size() - b.size() + 1;
        if (k < 0) return { 0 };
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        b.resize(k), a = a * Inv(b);
        a.resize(k), reverse(a.begin(), a.end());
        return a;
    }
    pair<Poly, Poly> operator%(Poly a, const Poly& b) {
        Poly c = a / b;
        a -= b * c, a.resize(b.size() - 1);
        return { c, a };
    }

    // 多项式求导积分
    Poly deriv(Poly a) {
        fp(i, 1, a.size() - 1) a[i - 1] = MUL(i, a[i]);
        return a.pop_back(), a;
    }
    Poly integ(Poly a) {
        a.push_back(0);
        fd(i, a.size() - 1, 1) a[i] = MUL(inv[i], a[i - 1]);
        return a[0] = 0, a;
    }

    // 取ln
    Poly Ln(Poly a) {
        int n = a.size();
        a = deriv(a) * Inv(a);
        return a.resize(n - 1), integ(a);
    }

    // 取exp
    Poly Exp(Poly a) {
        int n = a.size(), k = norm(n);
        Poly b = { 1 }, c, d; a.resize(k);
        for (int L = 2; L <= k; L <<= 1) {
            d = b, b.resize(L), c = Ln(b), c.resize(L);
            fp(i, 0, L - 1) c[i] = a[i] - c[i] + (a[i] < c[i] ? P : 0);
            ADD(c[0], 1), DFT(b), DFT(c), dot(b, c), IDFT(b);
            move(d.begin(), d.end(), b.begin());
        }
        return b.resize(n), b;
    }

    // 开根
    Poly Sqrt(Poly a) {
        int n = a.size(), k = norm(n); a.resize(k);
        Poly b = { (new Cipolla(P))->sqrt(a[0]).first, 0 }, c;
        for (int L = 2; L <= k; L <<= 1) {
            b.resize(L), c = Poly(a.begin(), a.begin() + L) * Inv2k(b);
            fp(i, L / 2, L - 1) b[i] = MUL(c[i], (P + 1) / 2);
        }
        return b.resize(n), b;
    }

    // 多项式快速幂
    Poly Pow1(Poly& a, int b) { return Exp(Ln(a) * b); } // a[0] = 1, 循环卷积
    Poly Pow2(Poly& a, int b) {
        int n = (a.size() - 1) * b + 1, L = norm(n);
        a.resize(L);
        DFT(a);
        fp(i, 0, L - 1) a[i] = qpow(a[i], b);
        IDFT(a);
        return a;
    }
    Poly Pow(Poly a, int b1, int b2) { // b1 = b % P, b2 = b % phi(P) and b >= n if a[0] > 0
        int n = a.size(), d = 0, k;
        while (d < n && !a[d]) ++d;
        if ((ll)d * b1 >= n) return Poly(n);
        a.erase(a.begin(), a.begin() + d);
        k = qpow(a[0]), norm(a *= k);
        a = Pow1(a, b1) * qpow(k, P - 1 - b2);
        a.resize(n), d *= b1;
        fd(i, n - 1, 0) a[i] = i >= d ? a[i - d] : 0;
        return a;
    }
}
using namespace Polynomial;

int infac[N], fac[N];

void init() {
    infac[0] = fac[0] = 1;
    for (int i = 1; i < N; i ++ ) {
        fac[i] = fac[i - 1] * i % P;
        infac[i] = infac[i - 1] * inv[i] % P;
    }
}

int C(int a, int b) {
    if (a < 0 || b < 0 || a < b) return 0;
    return fac[a] * infac[b] % P * infac[a - b] % P;
}

int A(int a, int b) {
    if (a < b || a < 0 || b < 0) return 0;
    return fac[a] * infac[a - b] % P;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    init();
    int n, m;
    cin >> n >> m;
    Poly g(m + 1);
    int ans = 0;
    for(int i = 0; i <= m; ++i) g[i] = A(m, i) * C(m, i) % P;
    Poly f = Pow2(g, n);
    for (int i = 0; i <= n * m; i ++ ) {
        if (i & 1) ans -= fac[n * m - i] * f[i] % P;
        else ans += fac[n * m - i] * f[i] % P;
        ans = (ans % P + P) % P;
    }
    cout << ans << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 48ms
memory: 92100kb

input:

2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 66ms
memory: 91988kb

input:

5 1

output:

44

result:

ok 1 number(s): "44"

Test #3:

score: 0
Accepted
time: 54ms
memory: 92532kb

input:

167 91

output:

284830080

result:

ok 1 number(s): "284830080"

Test #4:

score: 0
Accepted
time: 53ms
memory: 92024kb

input:

2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 46ms
memory: 92096kb

input:

2 3

output:

36

result:

ok 1 number(s): "36"

Test #6:

score: 0
Accepted
time: 46ms
memory: 91980kb

input:

2 4

output:

576

result:

ok 1 number(s): "576"

Test #7:

score: 0
Accepted
time: 44ms
memory: 91972kb

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #8:

score: 0
Accepted
time: 49ms
memory: 92036kb

input:

3 2

output:

80

result:

ok 1 number(s): "80"

Test #9:

score: 0
Accepted
time: 51ms
memory: 91952kb

input:

3 3

output:

12096

result:

ok 1 number(s): "12096"

Test #10:

score: 0
Accepted
time: 49ms
memory: 92060kb

input:

3 4

output:

4783104

result:

ok 1 number(s): "4783104"

Test #11:

score: 0
Accepted
time: 50ms
memory: 92104kb

input:

4 1

output:

9

result:

ok 1 number(s): "9"

Test #12:

score: 0
Accepted
time: 55ms
memory: 92188kb

input:

4 2

output:

4752

result:

ok 1 number(s): "4752"

Test #13:

score: 0
Accepted
time: 55ms
memory: 92032kb

input:

4 3

output:

17927568

result:

ok 1 number(s): "17927568"

Test #14:

score: 0
Accepted
time: 51ms
memory: 92036kb

input:

4 4

output:

776703752

result:

ok 1 number(s): "776703752"

Test #15:

score: 0
Accepted
time: 57ms
memory: 92112kb

input:

5 2

output:

440192

result:

ok 1 number(s): "440192"

Test #16:

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

input:

5 3

output:

189125068

result:

ok 1 number(s): "189125068"

Test #17:

score: 0
Accepted
time: 53ms
memory: 91952kb

input:

5 4

output:

975434093

result:

ok 1 number(s): "975434093"

Test #18:

score: 0
Accepted
time: 147ms
memory: 108324kb

input:

1000 1000

output:

720037464

result:

ok 1 number(s): "720037464"

Test #19:

score: 0
Accepted
time: 60ms
memory: 91968kb

input:

72 42

output:

638177567

result:

ok 1 number(s): "638177567"

Test #20:

score: 0
Accepted
time: 48ms
memory: 92192kb

input:

15 19

output:

663050288

result:

ok 1 number(s): "663050288"

Test #21:

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

input:

68 89

output:

94365047

result:

ok 1 number(s): "94365047"

Test #22:

score: 0
Accepted
time: 52ms
memory: 92124kb

input:

92 37

output:

652605307

result:

ok 1 number(s): "652605307"

Test #23:

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

input:

61 87

output:

498277867

result:

ok 1 number(s): "498277867"

Test #24:

score: 0
Accepted
time: 46ms
memory: 91972kb

input:

81 40

output:

133095344

result:

ok 1 number(s): "133095344"

Test #25:

score: 0
Accepted
time: 52ms
memory: 92044kb

input:

7 91

output:

524164813

result:

ok 1 number(s): "524164813"

Test #26:

score: 0
Accepted
time: 50ms
memory: 91976kb

input:

31 18

output:

361233485

result:

ok 1 number(s): "361233485"

Test #27:

score: 0
Accepted
time: 54ms
memory: 92032kb

input:

74 54

output:

500686087

result:

ok 1 number(s): "500686087"

Test #28:

score: 0
Accepted
time: 56ms
memory: 92116kb

input:

32 2

output:

586504335

result:

ok 1 number(s): "586504335"

Test #29:

score: 0
Accepted
time: 80ms
memory: 100308kb

input:

656 718

output:

346764298

result:

ok 1 number(s): "346764298"

Test #30:

score: 0
Accepted
time: 79ms
memory: 96056kb

input:

254 689

output:

358078813

result:

ok 1 number(s): "358078813"

Test #31:

score: 0
Accepted
time: 93ms
memory: 100076kb

input:

713 674

output:

914437613

result:

ok 1 number(s): "914437613"

Test #32:

score: 0
Accepted
time: 50ms
memory: 94012kb

input:

136 698

output:

56687290

result:

ok 1 number(s): "56687290"

Test #33:

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

input:

369 401

output:

312325811

result:

ok 1 number(s): "312325811"

Test #34:

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

input:

280 204

output:

280012063

result:

ok 1 number(s): "280012063"

Test #35:

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

input:

904 225

output:

162909174

result:

ok 1 number(s): "162909174"

Test #36:

score: 0
Accepted
time: 122ms
memory: 108304kb

input:

855 928

output:

39885159

result:

ok 1 number(s): "39885159"

Test #37:

score: 0
Accepted
time: 75ms
memory: 96192kb

input:

503 365

output:

745115888

result:

ok 1 number(s): "745115888"

Test #38:

score: 0
Accepted
time: 133ms
memory: 108376kb

input:

646 996

output:

610925577

result:

ok 1 number(s): "610925577"

Test #39:

score: 0
Accepted
time: 143ms
memory: 108252kb

input:

990 918

output:

203469632

result:

ok 1 number(s): "203469632"

Test #40:

score: 0
Accepted
time: 145ms
memory: 108252kb

input:

961 949

output:

169566857

result:

ok 1 number(s): "169566857"

Test #41:

score: 0
Accepted
time: 132ms
memory: 108388kb

input:

946 932

output:

352423195

result:

ok 1 number(s): "352423195"

Test #42:

score: 0
Accepted
time: 142ms
memory: 108400kb

input:

903 981

output:

196309824

result:

ok 1 number(s): "196309824"

Test #43:

score: 0
Accepted
time: 125ms
memory: 108324kb

input:

916 988

output:

487208972

result:

ok 1 number(s): "487208972"

Test #44:

score: 0
Accepted
time: 138ms
memory: 108436kb

input:

982 982

output:

387421488

result:

ok 1 number(s): "387421488"

Test #45:

score: 0
Accepted
time: 138ms
memory: 108348kb

input:

955 911

output:

955637031

result:

ok 1 number(s): "955637031"

Test #46:

score: 0
Accepted
time: 144ms
memory: 108528kb

input:

906 999

output:

798469943

result:

ok 1 number(s): "798469943"

Test #47:

score: 0
Accepted
time: 139ms
memory: 108460kb

input:

982 975

output:

193506289

result:

ok 1 number(s): "193506289"

Test #48:

score: 0
Accepted
time: 141ms
memory: 108324kb

input:

921 991

output:

431202149

result:

ok 1 number(s): "431202149"