QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#628704 | #1423. Bin | ohwphil | AC ✓ | 7474ms | 102856kb | C++17 | 8.1kb | 2024-10-10 21:47:34 | 2024-10-10 21:48:36 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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"