QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628704#1423. BinohwphilAC ✓7474ms102856kbC++178.1kb2024-10-10 21:47:342024-10-10 21:48:36

Judging History

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

  • [2024-10-10 21:48:36]
  • 评测
  • 测评结果:AC
  • 用时:7474ms
  • 内存:102856kb
  • [2024-10-10 21:47:34]
  • 提交

answer

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

// ref: https://judge.yosupo.jp/submission/102040

template<int M> struct MINT {
    long long v;
    static MINT<M> w;
    MINT<M>() : v(0) {}
    MINT<M>(const long long v) : v(v) { normalize(); }
    void normalize() { v %= M; if (v < 0) v += M; }

    friend istream& operator >> (istream& in, MINT<M>& a) { in >> a.v; a.normalize(); return in; }
    friend ostream& operator << (ostream& out, const MINT<M>& a) { return out << a.v; }
    friend MINT<M> pow(MINT<M> a, long long b) {
        MINT<M> res = 1;
        for (; b; b >>= 1, a *= a) if (b & 1) res *= a;
        return res;
    }

    MINT<M> power(long long b) const { return pow(*this, b); }
    MINT<M> mul_inv() const { return power(M - 2); }

    MINT<M>& operator += (const MINT<M>& t) { if ((v += t.v) >= M) v -= M; return *this; }
    MINT<M>& operator -= (const MINT<M>& t) { if ((v -= t.v) < 0) v += M; return *this; }
    MINT<M>& operator *= (const MINT<M>& t) { v *= t.v; normalize(); return *this; }
    MINT<M>& operator /= (const MINT<M>& t) { *this *= t.mul_inv(); normalize(); return *this; }

    MINT<M> operator + (const MINT<M>& t) const { return MINT<M>(*this) += t; }
    MINT<M> operator - (const MINT<M>& t) const { return MINT<M>(*this) -= t; }
    MINT<M> operator * (const MINT<M>& t) const { return MINT<M>(*this) *= t; }
    MINT<M> operator / (const MINT<M>& t) const { return MINT<M>(*this) /= t; }
    MINT<M> operator - () const { return -v; }

    bool operator == (const MINT<M>& t) const { return v == t.v; }
    bool operator != (const MINT<M>& t) const { return v != t.v; }

    operator int32_t() const { return v; }
    operator int64_t() const { return v; }
};

template<int M>
void NTT(vector<MINT<M>>& a, bool inv_fft = false) {
    int n = a.size(); vector<MINT<M>> root(n / 2);
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n / 2;
        while (j >= bit) j -= bit, bit >>= 1;
        if (i < (j += bit)) swap(a[i], a[j]);
    }
    auto ang = MINT<M>::w.power((M - 1) / n); if (inv_fft) ang = ang.mul_inv();
    root[0] = 1; for (int i = 1; i < n / 2; i++) root[i] = root[i - 1] * ang;
    for (int i = 2; i <= n; i <<= 1) {
        int step = n / i;
        for (int j = 0; j < n; j += i) {
            for (int k = 0; k < i / 2; k++) {
                auto u = a[j + k], v = a[j + k + i / 2] * root[k * step];
                a[j + k] = u + v; a[j + k + i / 2] = u - v;
            }
        }
    }
    auto inv = MINT<M>(n).mul_inv();
    if (inv_fft) for (int i = 0; i < n; i++) a[i] = a[i] * inv;
}

template<typename T>
struct Poly {
    vector<T> a;
    Poly() : a() {}
    Poly(T a0) : a(1, a0) { normalize(); }
    Poly(const vector<T>& a) : a(a) { normalize(); }
    void normalize() { while (!a.empty() && a.back() == T(0)) a.pop_back(); }

    int size() const { return a.size(); }
    int deg() const { return size() - 1; }
    void push_back(const T& x) { a.push_back(x); }
    T get(int idx) const { return 0 <= idx && idx < size() ? a[idx] : T(0); }
    T& operator [] (int idx) { return a[idx]; }

    Poly reversed() const { auto b = a; reverse(b.begin(), b.end()); return b; }
    Poly trim(int sz) const { return vector<T>(a.begin(), a.begin() + min(sz, size())); }
    Poly inv(int n) const {
        Poly q(T(1) / a[0]);
        for (int i = 1; i < n; i <<= 1) {
            Poly p = Poly(2) - q * trim(i * 2);
            q = (p * q).trim(i * 2);
        }
        return q.trim(n);
    }

    Poly operator *= (const T& x) { for (auto& i : a) i *= x; normalize(); return *this; }
    Poly operator /= (const T& x) { return *this *= T(1) / x; }

    Poly operator += (const Poly& t) {
        a.resize(max(size(), t.size()));
        for (int i = 0; i < t.size(); i++) a[i] += t.a[i];
        normalize(); return *this;
    }
    Poly operator -= (const Poly& t) {
        a.resize(max(size(), t.size()));
        for (int i = 0; i < t.size(); i++) a[i] -= t.a[i];
        normalize(); return *this;
    }
    Poly operator *= (const Poly& t) {
        auto b = t.a;
        int n = 2; while (n < a.size() + b.size()) n <<= 1;
        a.resize(n); b.resize(n); NTT(a); NTT(b);
        for (int i = 0; i < n; i++) a[i] *= b[i];
        NTT(a, true); normalize(); return *this;
    }
    Poly operator /= (const Poly& t) {
        if (deg() < t.deg()) return *this = Poly();
        int sz = deg() - t.deg() + 1;
        Poly ra = reversed().trim(sz), rb = t.reversed().trim(sz).inv(sz);
        *this = (ra * rb).trim(sz);
        for (int i = sz - size(); i; i--) a.push_back(T(0));
        reverse(a.begin(), a.end()); normalize();
        return *this;
    }
    Poly operator %= (const Poly& t) {
        if (deg() < t.deg()) return *this;
        Poly tmp = *this; tmp /= t; tmp *= t;
        *this -= tmp; normalize();
        return *this;
    }

    Poly operator + (const Poly& t) const { return Poly(*this) += t; }
    Poly operator - (const Poly& t) const { return Poly(*this) -= t; }
    Poly operator * (const Poly& t) const { return Poly(*this) *= t; }
    Poly operator / (const Poly& t) const { return Poly(*this) /= t; }
    Poly operator % (const Poly& t) const { return Poly(*this) %= t; }
    Poly operator * (const T x) const { return Poly(*this) *= x; }
    Poly operator / (const T x) const { return Poly(*this) /= x; }

    T eval(T x) const {
        T res = 0;
        for (int i = deg(); i >= 0; i--) res = res * x + a[i];
        return res;
    }
    Poly derivative() const {
        vector<T> res;
        for (int i = 1; i < size(); i++) res.push_back(T(i) * a[i]);
        return res;
    }
    Poly integral() const {
        vector<T> res{ T(0) };
        for (int i = 0; i < size(); i++) res.push_back(a[i] / T(i + 1));
        return res;
    }
    Poly ln(int n) const {
        assert(size() > 0 && a[0] == T(1));
        return (derivative() * inv(n)).integral().trim(n);
    }
    Poly exp(int n) const {
        if (size() == 0) return Poly(1);
        assert(size() > 0 && a[0] == T(0));
        Poly res(1);
        for (int i = 1; i < n; i <<= 1) {
            auto t = Poly(1) + trim(i * 2) - res.ln(i * 2);
            res = (res * t).trim(i * 2);
        }
        return res.trim(n);
    }
    Poly pow(long long n, int k) const {
        // compute f(x)^n mod x^k
        Poly acc(1), t = *this;
        t = t.trim(k);
        for (; n; n >>= 1) {
            if (n & 1) acc = (acc * t).trim(k);
            t = (t * t).trim(k);
        }
        return acc;
    }
};

using ModInt = MINT<998244353>;
template<> ModInt ModInt::w = ModInt(3);

using T = ModInt;


const int MAX_SIZE = 1 << 20;
int N, K;

vector<ModInt> T_array(MAX_SIZE);

void DnC(int l, int r) {
    if (l + 1 == r) {
        if (l <= 1) {
            T_array[l] = l;
        }
        else {
            if (l % 2 == 0) {
                T_array[l] -= T_array[l / 2] * T_array[l / 2];
            }
            T_array[l] /= 2;
            int curr_i = (l + 1) / 2;
            while (curr_i < l && (2 * curr_i - l) <= K) {
                T_array[l] += T_array[curr_i] * T_array[l - curr_i];
                ++curr_i;
            }
        }
        return;
    }
    int m = l + r >> 1;
    DnC(l, m);
    vector<ModInt> A(T_array.begin() + l, T_array.begin() + m);
    int len1 = min(m, r - l);
    int len2 = min(l, r - l);
    vector<ModInt> B(T_array.begin(), T_array.begin() + len1);
    vector<ModInt> C(T_array.begin(), T_array.begin() + len2);
    Poly<ModInt> PA(A), PB(B), PC(C);
    Poly<ModInt> prod1 = PA * PB;
    Poly<ModInt> prod2 = PA * PC;
    for (int offset = m - l; offset < r - l; ++offset) {
        if (prod1.size() > offset) {
            T_array[offset + l] += prod1[offset];
        }
        if (prod2.size() > offset) {
            T_array[offset + l] += prod2[offset];
        }
    }
    DnC(m, r);
}

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

    cin >> N >> K;

    DnC(0, MAX_SIZE);

    cout << T_array[N] << '\n';

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 7259ms
memory: 102732kb

input:

2 0

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 7260ms
memory: 102548kb

input:

3 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 7232ms
memory: 102732kb

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 7283ms
memory: 102732kb

input:

4 0

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 7260ms
memory: 102716kb

input:

4 1

output:

3

result:

ok 1 number(s): "3"

Test #6:

score: 0
Accepted
time: 7249ms
memory: 102696kb

input:

4 2

output:

5

result:

ok 1 number(s): "5"

Test #7:

score: 0
Accepted
time: 7280ms
memory: 102744kb

input:

6 2

output:

23

result:

ok 1 number(s): "23"

Test #8:

score: 0
Accepted
time: 7293ms
memory: 102600kb

input:

7 42

output:

132

result:

ok 1 number(s): "132"

Test #9:

score: 0
Accepted
time: 7312ms
memory: 102480kb

input:

10 1

output:

400

result:

ok 1 number(s): "400"

Test #10:

score: 0
Accepted
time: 7313ms
memory: 102728kb

input:

13 4

output:

42003

result:

ok 1 number(s): "42003"

Test #11:

score: 0
Accepted
time: 7312ms
memory: 102776kb

input:

239 17

output:

385818773

result:

ok 1 number(s): "385818773"

Test #12:

score: 0
Accepted
time: 7382ms
memory: 102856kb

input:

50216 58

output:

744498776

result:

ok 1 number(s): "744498776"

Test #13:

score: 0
Accepted
time: 7395ms
memory: 102592kb

input:

787788 78

output:

394429402

result:

ok 1 number(s): "394429402"

Test #14:

score: 0
Accepted
time: 7436ms
memory: 102792kb

input:

5 92

output:

14

result:

ok 1 number(s): "14"

Test #15:

score: 0
Accepted
time: 7391ms
memory: 102780kb

input:

88 79

output:

931161641

result:

ok 1 number(s): "931161641"

Test #16:

score: 0
Accepted
time: 7424ms
memory: 102676kb

input:

749 77

output:

615055472

result:

ok 1 number(s): "615055472"

Test #17:

score: 0
Accepted
time: 7474ms
memory: 102632kb

input:

2281 89

output:

282226588

result:

ok 1 number(s): "282226588"

Test #18:

score: 0
Accepted
time: 7462ms
memory: 102756kb

input:

5765 35

output:

293680396

result:

ok 1 number(s): "293680396"

Test #19:

score: 0
Accepted
time: 7361ms
memory: 102700kb

input:

43189 12

output:

805295564

result:

ok 1 number(s): "805295564"

Test #20:

score: 0
Accepted
time: 7281ms
memory: 102816kb

input:

806855 5

output:

593114139

result:

ok 1 number(s): "593114139"

Test #21:

score: 0
Accepted
time: 7296ms
memory: 102680kb

input:

994514 45

output:

678426421

result:

ok 1 number(s): "678426421"

Test #22:

score: 0
Accepted
time: 7420ms
memory: 102832kb

input:

999921 62

output:

752162081

result:

ok 1 number(s): "752162081"

Test #23:

score: 0
Accepted
time: 7367ms
memory: 102544kb

input:

995033 94

output:

130314865

result:

ok 1 number(s): "130314865"

Test #24:

score: 0
Accepted
time: 7362ms
memory: 102636kb

input:

901438 97

output:

809128292

result:

ok 1 number(s): "809128292"

Test #25:

score: 0
Accepted
time: 7244ms
memory: 102700kb

input:

993020 0

output:

926771801

result:

ok 1 number(s): "926771801"

Test #26:

score: 0
Accepted
time: 7382ms
memory: 102556kb

input:

1000000 100

output:

470305140

result:

ok 1 number(s): "470305140"