結果

問題 No.2763 Macaron Gift Box
コンテスト
ユーザー hiro1729
提出日時 2024-05-17 22:11:23
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 179 ms / 3,000 ms
コード長 2,667 bytes
コンパイル時間 5,352 ms
コンパイル使用メモリ 291,896 KB
実行使用メモリ 20,172 KB
最終ジャッジ日時 2024-12-20 14:03:43
合計ジャッジ時間 7,411 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
#include <atcoder/convolution>
using namespace atcoder;
using mint = modint998244353;

#define rep(i, n) for (int i = 0; i < (n); i++)

// Formal Power Series
using vm = vector<mint>;
struct fps : vm {
#define d (*this)
#define s int(vm::size())
  template<class...Args> fps(Args...args): vm(args...) {}
  fps(initializer_list<mint> a): vm(a.begin(),a.end()) {}
  void rsz(int n) { if (s < n) resize(n);}
  fps& low_(int n) { resize(n); return d;}
  fps low(int n) const { return fps(d).low_(n);}
  mint& operator[](int i) { rsz(i+1); return vm::operator[](i);}
  mint operator[](int i) const { return i<s ? vm::operator[](i) : 0;}
  mint operator()(mint x) const {
    mint r;
    for (int i = s-1; i >= 0; --i) r = r*x+d[i];
    return r;
  }
  fps operator-() const { fps r(d); rep(i,s) r[i] = -r[i]; return r;}
  fps& operator+=(const fps& a) { rsz(a.size()); rep(i,a.size()) d[i] += a[i]; return d;}
  fps& operator-=(const fps& a) { rsz(a.size()); rep(i,a.size()) d[i] -= a[i]; return d;}
  fps& operator*=(const fps& a) { return d = convolution(d, a);}
  fps& operator*=(mint a) { rep(i,s) d[i] *= a; return d;}
  fps& operator/=(mint a) { rep(i,s) d[i] /= a; return d;}
  fps operator+(const fps& a) const { return fps(d) += a;}
  fps operator-(const fps& a) const { return fps(d) -= a;}
  fps operator*(const fps& a) const { return fps(d) *= a;}
  fps operator*(mint a) const { return fps(d) *= a;}
  fps operator/(mint a) const { return fps(d) /= a;}
  fps operator~() const {
    fps r({d[0].inv()});
    for (int i = 1; i < s; i <<= 1) r = r*mint(2) - (r*r*low(i<<1)).low(i<<1);
    return r.low_(s);
  }
  fps& operator/=(const fps& a) { int w = s; d *= ~a; return d.low_(w);}
  fps operator/(const fps& a) const { return fps(d) /= a;}
  fps integ() const {
    fps r;
    rep(i,s) r[i+1] = d[i]/(i+1);
    return r;
  }
#undef s
#undef d
};
ostream& operator<<(ostream&o,const fps&a) {
  rep(i,a.size()) o<<(i?" ":"")<<a[i].val();
  return o;
}

int main() {
	long long N, K;
	cin >> N >> K;
	vm A(N + 1), B(N + 1);
	A[0] = 1;
	B[0] = 1;
	for (int c = 1, p = 1, s = 4; p <= N; p += s, s += 3, c++) {
		if (c % 2 == 0) {
			if (p <= N) A[p] = 1;
			if (p + c <= N) A[p + c] = 1;
		} else {
			if (p <= N) A[p] = -1;
			if (p + c <= N) A[p + c] = -1;
		}
		if (c % 2 == 0) {
			if (p * (K + 1) <= N) B[p * (K + 1)] = 1;
			if ((p + c) * (K + 1) <= N) B[(p + c) * (K + 1)] = 1;
		} else {
			if (p * (K + 1) <= N) B[p * (K + 1)] = -1;
			if ((p + c) * (K + 1) <= N) B[(p + c) * (K + 1)] = -1;
		}
	}
	fps c = fps(B) / fps(A);
	for (int i = 1; i <= N; i++) cout << c[i].val() << ' ';
}
0