結果

問題 No.2763 Macaron Gift Box
ユーザー KudeKude
提出日時 2024-05-17 23:09:54
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 117 ms / 3,000 ms
コード長 10,320 bytes
コンパイル時間 3,981 ms
コンパイル使用メモリ 287,700 KB
実行使用メモリ 19,656 KB
最終ジャッジ日時 2024-05-17 23:10:01
合計ジャッジ時間 5,902 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
11,208 KB
testcase_01 AC 14 ms
11,204 KB
testcase_02 AC 16 ms
11,204 KB
testcase_03 AC 14 ms
11,212 KB
testcase_04 AC 16 ms
11,336 KB
testcase_05 AC 15 ms
11,336 KB
testcase_06 AC 14 ms
11,332 KB
testcase_07 AC 62 ms
15,048 KB
testcase_08 AC 26 ms
12,104 KB
testcase_09 AC 38 ms
13,000 KB
testcase_10 AC 113 ms
19,404 KB
testcase_11 AC 115 ms
19,528 KB
testcase_12 AC 117 ms
19,656 KB
testcase_13 AC 116 ms
19,656 KB
testcase_14 AC 25 ms
11,976 KB
testcase_15 AC 28 ms
11,972 KB
testcase_16 AC 25 ms
12,100 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:49:6: warning: '{anonymous}::mint {anonymous}::perm(int, int)' defined but not used [-Wunused-function]
   49 | mint perm(int n, int k) {
      |      ^~~~
main.cpp:48:6: warning: '{anonymous}::mint {anonymous}::fact(int)' defined but not used [-Wunused-function]
   48 | mint fact(int n) {return Fact[n];}
      |      ^~~~
main.cpp:44:6: warning: '{anonymous}::mint {anonymous}::icomb(int, int)' defined but not used [-Wunused-function]
   44 | mint icomb(int n, int k) {
      |      ^~~~~
main.cpp:37:6: warning: '{anonymous}::mint {anonymous}::comb(int, int)' defined but not used [-Wunused-function]
   37 | mint comb(int n, int k) {
      |      ^~~~

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using mint = modint998244353;

constexpr int FACT_SIZE = 1000000;
mint Fact[FACT_SIZE + 1];
mint iFact[FACT_SIZE + 1];
const auto fact_init = [] {
    Fact[0] = mint::raw(1);
    for(int i = 1; i <= FACT_SIZE; ++i) {
        Fact[i] = Fact[i-1] * i;
    }
    iFact[FACT_SIZE] = Fact[FACT_SIZE].inv();
    for(int i = FACT_SIZE; i; --i) {
        iFact[i-1] = iFact[i] * i;
    }
    return false;
}();

mint comb(int n, int k) {
    if (k == 0) return mint::raw(1);
    assert(n >= 0 && k >= 0);
    if (k > n) return mint::raw(0);
    return Fact[n] * iFact[n - k] * iFact[k];
}

mint icomb(int n, int k) {
    return iFact[n] * Fact[n - k] * Fact[k];
}

mint fact(int n) {return Fact[n];}
mint perm(int n, int k) {
    assert(0 <= n);
    return Fact[n] * iFact[n - k];
}


template <class T>
struct FPS : vector<T> {
  using vector<T>::vector;

  FPS& operator+=(const FPS& f) {
    const int tsz = this->size(), fsz = f.size();
    const int csz = min(tsz, fsz);
    for (int i = 0; i < csz; i++) (*this)[i] += f[i];
    if (csz < fsz) {
      this->insert(this->end(), f.begin() + csz, f.end());
    }
    return *this;
  }
  FPS& operator+=(FPS&& f) {
    if (this->size() < f.size()) swap(*this, f);
    *this += f;
    return *this;
  }
  friend FPS operator+(const FPS& f, const FPS& g) {
    FPS h;
    h.reserve(max(f.size(), g.size()));
    h = f;
    h += g;
    return h;
  }
  friend FPS operator+(FPS&& f, const FPS& g) { return move(f += g); }
  friend FPS operator+(const FPS& f, FPS&& g) { return move(g += f); }
  friend FPS operator+(FPS&& f, FPS&& g) { return move(f += move(g)); }

  FPS& operator-=(const FPS& f) {
    const int tsz = this->size(), fsz = f.size();
    const int csz = min(tsz, fsz);
    for (int i = 0; i < csz; i++) (*this)[i] -= f[i];
    if (csz < fsz) {
      this->resize(fsz);
      for (int i = csz; i < fsz; i++) (*this)[i] = -f[i];
    }
    return *this;
  }
  FPS& operator-=(FPS&& f) {
    const int tsz = this->size(), fsz = f.size();
    if (tsz > fsz) {
      *this -= f;
    } else {
      for (int i = 0; i < tsz; i++) f[i] = (*this)[i] - f[i];
      for (int i = tsz; i < fsz; i++) f[i] = -f[i];
      swap(*this, f);
    }
    return *this;
  }
  friend FPS operator-(const FPS& f, const FPS& g) {
    FPS h;
    h.reserve(max(f.size(), g.size()));
    h = f;
    h -= g;
    return h;
  }
  friend FPS operator-(FPS&& f, const FPS& g) { return move(f -= g); }
  friend FPS operator-(const FPS& f, FPS&& g) {
    const int fsz = f.size(), gsz = g.size();
    const int csz = min(fsz, gsz);
    for (int i = 0; i < csz; i++) g[i] = f[i] - g[i];
    if (fsz < gsz) {
      for (int i = csz; i < gsz; i++) g[i] = -g[i];
    } else {
      g.insert(g.end(), f.begin() + csz, f.end());
    }
    return move(g);
  }
  friend FPS operator-(FPS&& f, FPS&& g) { return move(f -= move(g)); }
  FPS operator+() && { return move(*this); }
  FPS operator+() const& { return *this; }
  FPS operator-() && {
    for (T& x: *this) x = -x;
    return move(*this);
  }
  FPS operator-() const& {
    FPS f;
    f.reserve(this->size());
    for (const T& x: *this) f.emplace_back(-x);
    return f;
  }

  static void multiply_naive(FPS& f, const FPS& g) {
    int n = int(f.size()), m = int(g.size());
    if (n < m) {
      tmp1 = f;
      f.assign(n + m - 1, T());
      for (int j = m - 1; j >= 0; j--) {
        for (int i = n - 1; i >= 0; i--) {
          f[i + j] += tmp1[i] * g[j];
        }
      }
    } else {
      f.resize(n + m - 1);
      for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j > 0; j--) {
          f[i + j] += f[i] * g[j];
        }
        f[i] *= g[0];
      }
    }
  }

  static void multiply_fft(FPS& f, const FPS& g) {
    const int n = f.size(), m = g.size();
    const int z = bit_ceil(0U + n + m - 1);
    tmp1.reserve(z), tmp1 = g, tmp1.resize(z), internal::butterfly(tmp1);
    f.resize(z), internal::butterfly(f);
    for (int i = 0; i < z; i++) f[i] *= tmp1[i];
    internal::butterfly_inv(f);
    f.resize(n + m - 1);
    mint iz = mint(z).inv();
    for (int i = 0; i < n + m - 1; i++) f[i] *= iz;
  }

  FPS& operator*=(const FPS& f) {
    int n = int((*this).size()), m = int(f.size());
    if (!n || !m) {
      this->clear();
      return *this;
    };
    if (min(n, m) <= 60) multiply_naive(*this, f);
    else multiply_fft(*this, f);
    return *this;
  }
  FPS& operator*=(FPS&& f) {
    int n = int((*this).size()), m = int(f.size());
    if (this->size() < f.size()) swap(*this, f);
    return *this *= f;
  }
  friend FPS operator*(FPS&& f, FPS&& g) { return move(f *= move(g)); }
  friend FPS operator*(FPS&& f, const FPS& g) { return move(f *= g); }
  friend FPS operator*(const FPS& f, FPS&& g) { return move(g *= f); }
  friend FPS operator*(const FPS& f, const FPS& g) {
    int n = int(f.size()), m = int(g.size());
    if (!n || !m) return {};
    int z = bit_ceil(0U + n + m - 1);
    FPS h;
    h.reserve(z);
    h = f;
    h *= g;
    return h;
  }
  FPS& operator+=(T x) {
    if ((*this).empty()) (*this).emplace_back(x);
    else (*this)[0] += x;
    return *this;
  }
  friend FPS operator+(FPS f, T x) {
    f += x;
    return f;
  }
  friend FPS operator+(T x, FPS f) {
    f += x;
    return f;
  }
  FPS& operator-=(T x) {
    if ((*this).empty()) (*this).emplace_back(-x);
    else (*this)[0] -= x;
    return *this;
  }
  friend FPS operator-(FPS f, T x) {
    f -= x;
    return f;
  }
  friend FPS operator-(T x, FPS f) { return -move(f) + x; }
  FPS& operator*=(T x) {
    for (T& i: *this) i *= x;
    return *this;
  }
  friend FPS operator*(FPS f, T x) {
    f *= x;
    return f;
  }
  friend FPS operator*(T x, FPS f) {
    f *= x;
    return f;
  }
  FPS operator/=(T x) {
    if constexpr (internal::is_modint<T>::value) {
      T ix = x.inv();
      for (T& i: *this) i *= ix;
    } else {
      for (T& i: *this) i /= x;
    }
    return *this;
  }
  friend FPS operator/(FPS f, T x) {
    f /= x;
    return f;
  }
  FPS& operator<<=(int x) {
    assert(x >= 0);
    this->insert((*this).begin(), x, T());
    return *this;
  }
  friend FPS operator<<(const FPS& f, int x) {
    assert(x >= 0);
    const int fsz = f.size();
    FPS res;
    res.reserve(fsz + x);
    res.resize(x);
    res.insert(res.end(), f.begin(), f.end());
    return res;
  }
  friend FPS operator<<(FPS&& f, int x) {
    f <<= x;
    return move(f);
  }
  FPS& operator>>=(int x) {
    assert(x >= 0);
    const int tsz = this->size();
    if (x >= tsz) this->clear();
    else this->erase(this->begin(), this->begin() + x);
    return *this;
  }
  friend FPS operator>>(const FPS& f, int x) {
    assert(x >= 0);
    const int fsz = f.size();
    if (x >= fsz) return {};
    else return FPS(f.begin() + x, f.end());
  }
  friend FPS operator>>(FPS&& f, int x) {
    f >>= x;
    return move(f);
  }

  static FPS inv_proc(const FPS& f, FPS g, int len) {
    if (len == 0) {
      g.clear();
      return g;
    }
    FPS fi, gi;
    swap(fi, tmp2);
    swap(gi, tmp3);
    const int z = bit_ceil(0U + len);
    const int n = f.size();
    g.clear();
    g.reserve(z);
    fi.reserve(z);
    gi.reserve(z);

    assert(len >= 1 && n >= 1 && f[0] != 0);
    g.emplace_back(f[0] != 1 ? f[0].inv() : f[0]);
    const T inv2 = T(1) / 2;
    T i2k = 1;
    int m = 1;
    while (m != z) {
      const int m2 = 2 * m;
      fi.assign(f.begin(), f.begin() + min(n, m2));
      fi.resize(m2);
      internal::butterfly(fi);
      gi = g;
      gi.resize(m2);
      internal::butterfly(gi);
      for (int i = 0; i < m2; i++) fi[i] *= gi[i];
      internal::butterfly_inv(fi);
      fi.erase(fi.begin(), fi.begin() + m);
      fi.resize(m2);
      internal::butterfly(fi);
      for (int i = 0; i < m2; i++) fi[i] *= gi[i];
      internal::butterfly_inv(fi);
      i2k *= inv2;
      T c = -i2k * i2k;
      for (int i = 0; i < m; i++) {
        g.emplace_back(c * fi[i]);
      }
      m = m2;
    }
    g.resize(len);

    swap(fi, tmp2);
    swap(gi, tmp3);
    return g;
  }
  FPS inv(int len) const& {
    return inv_proc(*this, FPS(), len);
  }
  FPS inv(int len) && {
    tmp1 = *this;
    return inv_proc(tmp1, move(*this), len);
  }

  void Taylor_Shift_inplace(T c) {
    const int n = this->size();
    FPS f, g;
    swap(g, tmp2);
    swap(f, tmp3);
    f = *this;
    for (int i = 0; i < n; i++) f[i] *= Fact[i];
    T ck = 1;
    g.resize(n);
    for (int i = 0, j = n - 1; i < n; i++, j--, ck *= c) g[j] = ck * iFact[i];
    f *= g;
    for (int i = 0, j = n - 1; i < n; i++, j++) (*this)[i] = iFact[i] * f[j];
    swap(g, tmp2);
    swap(f, tmp3);
  }
  FPS Taylor_Shift(T c) const& { return FPS(*this).Taylor_Shift(c); }
  FPS Taylor_Shift(T c) && {
    this->Taylor_Shift_inplace(c);
    return move(*this);
  }

  void show(char sep = ' ', char end = '\n', bool flush = false) const {
    int sz = this->size();
    if (sz) {
      cout << (*this)[0].val();
      for (int i = 1; i < sz; i++) cout << sep << (*this)[i].val();
    }
    cout << end;
    if (flush) cout.flush();
  }

 private:
  inline static FPS tmp1, tmp2, tmp3;
};


} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  using fps = FPS<mint>;
  int n, k;
  cin >> n >> k;
  k++;
  fps f(n + 1);
  for (int i = 0;; i++) {
    int v = i * (3 * i - 1) / 2;
    if (v > n) break;
    f[v] = i % 2 ? -1 : 1;
  }
  for (int i = -1;; i--) {
    int v = i * (3 * i - 1) / 2;
    if (v > n) break;
    f[v] = i % 2 ? -1 : 1;
  }
  fps p(n + 1);
  for (int i = 0; i * k <= n; i++) p[i * k] = f[i];
  p *= f.inv(n + 1);
  for (int x = 1; x <= n; x++) cout << p[x].val() << " \n"[x == n];
}
0