提出 #33320070

---

ソースコード 拡げる

#include <bits/stdc++.h>

#define eprintf(args...) fprintf(stderr, args)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

const int mod = 998244353;

inline int qpow(int x, int n) {
	int ans = 1;
	for (; n; n >>= 1, x = 1LL * x * x % mod)
		if (n & 1) ans = 1LL * ans * x % mod;
	return ans;
}

namespace fft {
;

const int mxn = 1 << 19;
int N;
int r[mxn];
int w[mxn];
inline void init(int n) {
	N = n;
	for (int i = 1; i < n - 1; ++ i)
		r[i] = r[i >> 1] >> 1 | (i & 1 ? n >> 1 : 0);
	for (int h = 1; h < n; h <<= 1) {
		int temp = qpow(3, (mod - 1) / (h << 1));
		rep(i, h) w[h + i] = i ? 1LL * temp * w[h + i - 1] % mod : 1;
	}
}
inline void dft(int a[], int n) {
	if (N != n) init(n);
	for (int i = 1; i < n - 1; ++ i)
		if (i < r[i]) std::swap(a[i], a[r[i]]);
	for (int h = 1; h < n; h <<= 1)
		for (int i = 0; i < n; i += h << 1)
			for (int j = 0; j < h; ++ j) {
				int v = 1LL * a[i + h + j] * w[h + j] % mod;
				a[i + h + j] = a[i + j] - v >= 0 ? a[i + j] - v : a[i + j] + mod - v;
				a[i + j] = a[i + j] + v < mod ? a[i + j] + v : a[i + j] + v - mod;
			}
}
inline void idft(int a[], int n) {
	dft(a, n);
	std::reverse(a + 1, a + n);
	int iv = qpow(n, mod - 2);
	rep(i, n) a[i] = 1LL * a[i] * iv % mod;
}

} // fft

struct poly : std::vector <int> {
	poly() { clear(); }
	poly(size_t n) { assign(n, 0); }
	poly(std::vector <int> v) { clear(); for (int x : v) push_back(x); }
	poly(std::initializer_list <int> v) { clear(); for (int x : v) push_back(x); }
	inline poly modn(size_t n) const { poly p(*this); p.resize(n); return p; }
	friend inline poly operator + (const poly &a, const poly &b) {
		poly c(std::max(a.size(), b.size()));
		rep(i, a.size()) c[i] = (c[i] + a[i]) % mod;
		rep(i, b.size()) c[i] = (c[i] + b[i]) % mod;
		return c;
	}
	friend inline poly operator - (const poly &a, const poly &b) {
		poly c(std::max(a.size(), b.size()));
		rep(i, a.size()) c[i] = (c[i] + a[i]) % mod;
		rep(i, b.size()) c[i] = (c[i] + mod - b[i]) % mod;
		return c;
	}
	friend inline poly operator * (const poly &a, const poly &b) {
		poly c(a.size() + b.size() - 1);
		int sz = 1;
		for (; sz < (int) c.size(); sz <<= 1);
		if (1LL * a.size() * b.size() <= 64LL * sz) {
			rep(i, a.size()) rep(j, b.size()) c[i + j] = (c[i + j] + 1LL * a[i] * b[j]) % mod;
		} else {
			static int A[fft::mxn], B[fft::mxn];
			rep(i, sz) A[i] = i < (int) a.size() ? a[i] : 0;
			rep(i, sz) B[i] = i < (int) b.size() ? b[i] : 0;
			fft::dft(A, sz);
			fft::dft(B, sz);
			rep(i, sz) A[i] = 1LL * A[i] * B[i] % mod;
			fft::idft(A, sz);
			rep(i, c.size()) c[i] = A[i];
		}
		return c;
	}
	friend inline poly inv(const poly &a) {
		if (a.size() == 1) return {qpow(a[0], mod - 2)};
		int n = a.size(), n0 = (n + 1) >> 1;
		poly a0 = a.modn(n0);
		poly b0 = inv(a0);
		return (b0 + b0 - a * b0 * b0).modn(n);
	}
};

const int mxn = 3e5 + 5;
int fac[mxn], ifac[mxn];

inline int comb(int n, int m) {
	return m < 0 || m > n ? 0 : 1LL * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int n, K, a[mxn], cnt[mxn];

inline poly conq1(int l, int r) {
	if (l + 1 == r) {
		if (!cnt[l]) return {1};
		poly z(cnt[l] + 1);
		for (int i = 1; i <= cnt[l]; ++ i)
			z[i] = 1LL * fac[cnt[l]] * ifac[i] % mod * comb(cnt[l] - 1, cnt[l] - i) % mod;
		return z;
	}
	int m = (l + r) >> 1;
	return conq1(l, m) * conq1(m, r);
}

inline poly solve1() {
	poly g = conq1(0, n);
	rep(i, g.size()) g[i] = 1LL * g[i] * fac[i] % mod;
	poly f(n);
	rep(i, n) f[i] = g[n - i];
	return f;
}

inline poly solve2(poly g) {
	/*
	poly f(n);
	for (int i = 0; i < n; ++ i)
		for (int j = i; j < n; ++ j) {
			int cur = 1LL * comb(j, i) * g[j] % mod;
			if ((j - i) & 1) f[i] = (f[i] + mod - cur) % mod;
			else f[i] = (f[i] + cur) % mod;
		}
	return f;
	*/
	poly A(n), B(n);
	rep(i, n) A[i] = 1LL * g[i] * fac[i] % mod;
	rep(i, n) B[n - 1 - i] = 1LL * (i & 1 ? mod - 1 : 1) * ifac[i] % mod;
	poly C = A * B;
	poly f(n);
	rep(i, n) f[i] = 1LL * ifac[i] * C[i + n - 1] % mod;
	return f;
}

using frac = std::pair <poly, poly>;

inline frac conq3(const poly &c, int l, int r) {
	if (l + 1 == r) return {{c[l]}, {1, (mod - (n - 1 - l)) % mod}};
	int m = (l + r) >> 1;
	frac L = conq3(c, l, m), R = conq3(c, m, r);
	return {L.first * R.second + R.first * L.second, L.second * R.second};
}

inline poly solve3(poly c) {
	frac z = conq3(c, 0, n);
	poly f = ((z.first.modn(K)) * inv(z.second.modn(K))).modn(K);
	return f;
}

int main() {
	rep(i, mxn) fac[i] = i ? 1LL * i * fac[i - 1] % mod : 1;
	ifac[mxn - 1] = qpow(fac[mxn - 1], mod - 2);
	for (int i = mxn - 1; i; -- i) ifac[i - 1] = 1LL * i * ifac[i] % mod;
	scanf("%d %d", &n, &K), ++ K;
	rep(i, n) scanf("%d", &a[i]), -- a[i], cnt[a[i]] += 1;
	poly g = solve1();
	poly f = solve2(g);
	poly h = solve3(f);
	for (int i = 1; i < K; ++ i) printf("%d ", h[i]);
	printf("\n");
	return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘poly operator*(const poly&, const poly&)’:
./Main.cpp:74:33: warning: comparison of integer expressions of different signedness: ‘long long unsigned int’ and ‘long long int’ [-Wsign-compare]
   74 |   if (1LL * a.size() * b.size() <= 64LL * sz) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:165:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  165 |  scanf("%d %d", &n, &K), ++ K;
      |  ~~~~~^~~~~~~~~~~~~~~~~
./Main.cpp:166:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  166 |  rep(i, n) scanf("%d", &a[i]), -- a[i], cnt[a[i]] += 1;
      |            ~~~~~^~~~~~~~~~~~~

ジャッジ結果