結果

問題 No.2763 Macaron Gift Box
ユーザー hiro1729hiro1729
提出日時 2024-05-17 22:08:57
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,661 bytes
コンパイル時間 4,919 ms
コンパイル使用メモリ 322,592 KB
実行使用メモリ 20,424 KB
最終ジャッジ日時 2024-05-17 22:09:10
合計ジャッジ時間 7,048 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 73 ms
10,920 KB
testcase_08 AC 18 ms
6,944 KB
testcase_09 AC 37 ms
7,224 KB
testcase_10 RE -
testcase_11 RE -
testcase_12 AC 165 ms
20,424 KB
testcase_13 RE -
testcase_14 AC 18 ms
6,940 KB
testcase_15 AC 18 ms
6,944 KB
testcase_16 AC 17 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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() {
	int 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