結果
| 問題 |
No.2763 Macaron Gift Box
|
| コンテスト | |
| ユーザー |
 t98slider
|
| 提出日時 | 2024-05-19 04:44:23 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 112 ms / 3,000 ms |
| コード長 | 15,724 bytes |
| コンパイル時間 | 2,441 ms |
| コンパイル使用メモリ | 208,676 KB |
| 最終ジャッジ日時 | 2025-02-21 15:50:18 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 15 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<const unsigned int MOD> struct prime_modint {
using mint = prime_modint;
unsigned int v;
prime_modint() : v(0) {}
prime_modint(unsigned int a) { a %= MOD; v = a; }
prime_modint(unsigned long long a) { a %= MOD; v = a; }
prime_modint(int a) { a %= (int)(MOD); if(a < 0)a += MOD; v = a; }
prime_modint(long long a) { a %= (int)(MOD); if(a < 0)a += MOD; v = a; }
static constexpr int mod() { return MOD; }
mint& operator++() {v++; if(v == MOD)v = 0; return *this;}
mint& operator--() {if(v == 0)v = MOD; v--; return *this;}
mint operator++(int) { mint result = *this; ++*this; return result; }
mint operator--(int) { mint result = *this; --*this; return result; }
mint& operator+=(const mint& rhs) { v += rhs.v; if(v >= MOD) v -= MOD; return *this; }
mint& operator-=(const mint& rhs) { if(v < rhs.v) v += MOD; v -= rhs.v; return *this; }
mint& operator*=(const mint& rhs) {
v = (unsigned int)((unsigned long long)(v) * rhs.v % MOD);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint r = 1, x = *this;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const { assert(v); return pow(MOD - 2); }
friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; }
friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; }
friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; }
friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; }
friend bool operator==(const mint& lhs, const mint& rhs) { return (lhs.v == rhs.v); }
friend bool operator!=(const mint& lhs, const mint& rhs) { return (lhs.v != rhs.v); }
friend std::ostream& operator << (std::ostream &os, const mint& rhs) noexcept { return os << rhs.v; }
};
//using mint = prime_modint<1000000007>;
using mint = prime_modint<998244353>;
constexpr int bsf_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
template<class mint> struct fft_info {
const int g = primitive_root(mint::mod());
static constexpr int rank2 = bsf_constexpr(mint::mod() - 1);
std::array<mint, rank2 + 1> root; // root[i]^(2^i) == 1
std::array<mint, rank2 + 1> iroot; // root[i] * iroot[i] == 1
std::array<mint, std::max(0, rank2 - 2 + 1)> rate2;
std::array<mint, std::max(0, rank2 - 2 + 1)> irate2;
std::array<mint, std::max(0, rank2 - 3 + 1)> rate3;
std::array<mint, std::max(0, rank2 - 3 + 1)> irate3;
fft_info() {
root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
iroot[rank2] = root[rank2].inv();
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 2; i++) {
rate2[i] = root[i + 2] * prod;
irate2[i] = iroot[i + 2] * iprod;
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 3; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
}
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
constexpr int primitive_root(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) x /= i;
}
}
if (x > 1) divs[cnt++] = x;
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
void butterfly(std::vector<mint>& a) {
int n = int(a.size());
int h = ceil_pow2(n);
int len = 0; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len < h) {
if (h - len == 1) {
int p = 1 << (h - len - 1);
mint rot = 1;
for (int s = 0; s < (1 << len); s++) {
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * rot;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
if (s + 1 != (1 << len)) rot *= rate2[bsf(~(unsigned int)(s))];
}
len++;
} else {
// 4-base
int p = 1 << (h - len - 2);
mint rot = 1, imag = root[2];
for (int s = 0; s < (1 << len); s++) {
mint rot2 = rot * rot;
mint rot3 = rot2 * rot;
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto mod2 = 1ULL * mint::mod() * mint::mod();
auto a0 = 1ULL * a[i + offset].v;
auto a1 = 1ULL * a[i + offset + p].v * rot.v;
auto a2 = 1ULL * a[i + offset + 2 * p].v * rot2.v;
auto a3 = 1ULL * a[i + offset + 3 * p].v * rot3.v;
auto a1na3imag = 1ULL * mint(a1 + mod2 - a3).v * imag.v;
auto na2 = mod2 - a2;
a[i + offset] = a0 + a2 + a1 + a3;
a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
}
if (s + 1 != (1 << len))
rot *= rate3[bsf(~(unsigned int)(s))];
}
len += 2;
}
}
}
void butterfly_inv(std::vector<mint>& a) {
int n = int(a.size());
int h = ceil_pow2(n);
int len = h;
while (len) {
if (len == 1) {
int p = 1 << (h - len);
mint irot = 1;
for (int s = 0; s < (1 << (len - 1)); s++) {
int offset = s << (h - len + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] = (unsigned long long)(mint::mod() + l.v - r.v) * irot.v;
}
if (s + 1 != (1 << (len - 1))) irot *= irate2[bsf(~(unsigned int)(s))];
}
len--;
} else {
// 4-base
int p = 1 << (h - len);
mint irot = 1, iimag = iroot[2];
for (int s = 0; s < (1 << (len - 2)); s++) {
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = s << (h - len + 2);
for (int i = 0; i < p; i++) {
auto a0 = 1ULL * a[i + offset + 0 * p].v;
auto a1 = 1ULL * a[i + offset + 1 * p].v;
auto a2 = 1ULL * a[i + offset + 2 * p].v;
auto a3 = 1ULL * a[i + offset + 3 * p].v;
auto a2na3iimag = 1ULL * mint((mint::mod() + a2 - a3) * iimag.v).v;
a[i + offset] = a0 + a1 + a2 + a3;
a[i + offset + 1 * p] = (a0 + (mint::mod() - a1) + a2na3iimag) * irot.v;
a[i + offset + 2 * p] = (a0 + a1 + (mint::mod() - a2) + (mint::mod() - a3)) * irot2.v;
a[i + offset + 3 * p] = (a0 + (mint::mod() - a1) + (mint::mod() - a2na3iimag)) * irot3.v;
}
if (s + 1 != (1 << (len - 2))) irot *= irate3[bsf(~(unsigned int)(s))];
}
len -= 2;
}
}
}
std::vector<mint> convolution_naive(const std::vector<mint>& a, const std::vector<mint>& b) {
int n = int(a.size()), m = int(b.size());
std::vector<mint> ans(n + m - 1);
if (n < m) {
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
ans[i + j] += a[i] * b[j];
}
}
} else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i + j] += a[i] * b[j];
}
}
}
return ans;
}
std::vector<mint> convolution_fft(std::vector<mint> a, std::vector<mint> b) {
int n = int(a.size()), m = int(b.size());
int z = 1 << ceil_pow2(n + m - 1);
a.resize(z), butterfly(a);
b.resize(z), butterfly(b);
for (int i = 0; i < z; i++) a[i] *= b[i];
butterfly_inv(a);
a.resize(n + m - 1);
mint iz = mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
return a;
}
};
template <class mint> std::vector<mint> convolution(std::vector<mint>&& a, std::vector<mint>&& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
static fft_info<mint> info;
if (std::min(n, m) <= 60) return info.convolution_naive(a, b);
return info.convolution_fft(a, b);
}
template <unsigned int mod = 998244353, class T>
std::vector<T> convolution(const std::vector<T> &a, const std::vector<T> &b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
using mint = prime_modint<mod>;
std::vector<mint> a2(n), b2(m), c2;
for (int i = 0; i < n; i++) a2[i] = mint(a[i]);
for (int i = 0; i < m; i++) b2[i] = mint(b[i]);
static fft_info<mint> info;
if (std::min(n, m) <= 60) c2 = info.convolution_naive(a2, b2);
else c2 = info.convolution_fft(a2, b2);
std::vector<T> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) c[i] = c2[i].v;
return c;
}
template<class mint> struct Polynomial{
std::vector<mint> dat;
Polynomial() {}
Polynomial(int _size) : dat(_size) {}
Polynomial(std::vector<mint> rhs) : dat(rhs) {}
const mint& operator[](int p) const {
assert(0 <= p && p < dat.size());
return dat[p];
}
mint& operator[](int p) {
assert(0 <= p && p < dat.size());
return dat[p];
}
int size() { return dat.size(); }
Polynomial& operator+=(const Polynomial& rhs) {
int rn = rhs.dat.size();
if(dat.size() < rn) dat.resize(rn);
for(int i = 0; i < rn; i++) dat[i] += rhs.dat[i];
return *this;
}
Polynomial& operator-=(const Polynomial& rhs) {
int rn = rhs.dat.size();
if(dat.size() < rn) dat.resize(rn);
for(int i = 0; i < rn; i++) dat[i] -= rhs.dat[i];
return *this;
}
Polynomial& operator*=(const Polynomial& rhs) {
dat = convolution(dat, rhs.dat);
return *this;
}
Polynomial& operator/=(const Polynomial& rhs) {
// 未実装
return *this;
}
Polynomial operator+() const { return *this; }
Polynomial operator-() const { return Polynomial() - *this; }
Polynomial inv(){
assert(!dat.empty());
const int N = dat.size();
static fft_info<mint> info;
Polynomial invP(1);
invP.dat.reserve(N);
invP[0] = dat[0].inv();
while(invP.size() < N){
const int M = 2 * invP.size();
std::vector<mint> buf(M), finvP(M);
std::copy(dat.begin(), dat.begin() + min(M, N), buf.begin());
std::copy(invP.dat.begin(), invP.dat.end(), finvP.begin());
info.butterfly(buf);
info.butterfly(finvP);
for(int i = 0; i < M; i++) buf[i] *= finvP[i];
info.butterfly_inv(buf);
fill(buf.begin(), buf.begin() + invP.size(), 0);
info.butterfly(buf);
for(int i = 0; i < M; i++) buf[i] *= finvP[i];
info.butterfly_inv(buf);
mint coef = - (mint(1 - mint::mod()) / int(buf.size())).pow(2);
for (int i = invP.size(); i < min(M, N + 1); i++) invP.dat.push_back(buf[i] * coef);
}
return invP;
}
friend Polynomial operator+(const Polynomial& lhs, const Polynomial& rhs) {
return Polynomial(lhs) += rhs;
}
friend Polynomial operator-(const Polynomial& lhs, const Polynomial& rhs) {
return Polynomial(lhs) -= rhs;
}
friend Polynomial operator*(const Polynomial& lhs, const Polynomial& rhs) {
return Polynomial(lhs) *= rhs;
}
friend Polynomial operator/(const Polynomial& lhs, const Polynomial& rhs) {
return Polynomial(lhs) /= rhs;
}
Polynomial diff() const {
const int N = dat.size();
Polynomial res(std::max(0, N - 1));
mint coef(1);
for(int i = 1; i < N; i++, coef++) {
res[i - 1] = dat[i] * coef;
}
return res;
}
Polynomial integral() const {
const int N = dat.size();
Polynomial res(N + 1);
res[0] = mint(0);
if (N > 0) res[1] = mint(1);
auto mod = mint::mod();
for (int i = 2; i <= N; i++) res[i] = (-res[mod % i]) * (mod / i);
for (int i = 0; i < N; i++) res[i + 1] *= dat[i];
return res;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int N, K;
cin >> N >> K;
Polynomial<mint> P(N + 1), Q(N + 1);
Q[0] = 1;
for(int i = 1; i * (3 * i - 1) / 2 <= N; i++) {
Q[i * (3 * i - 1) / 2] = i & 1 ? -1 : 1;
}
for(int i = -1; i * (3 * i - 1) / 2 <= N; i--) {
Q[i * (3 * i - 1) / 2] = i & 1 ? -1 : 1;
}
for(int i = 0; i * (K + 1) <= N; i++){
P[i * (K + 1)] = Q[i];
}
P *= Q.inv();
for(int i = 1; i <= N; i++){
cout << P[i] << (i == N ? '\n' : ' ');
}
}