提出 #34934794

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

inline void uadd(int &x, int y)
{
	x += y - mod;
	x += x >> 31 & mod;
}

inline void umul(int &x, int y)
{
	x = 1LL * x * y % mod;
}

inline int add(int x, int y)
{
	return x + y < mod ? x + y : x + y - mod;
}

inline int mul(int x, int y)
{
	return 1LL * x * y % mod;
}

inline int qpow(int x, int n)
{
	int ans = 1;
	for (; n; n >>= 1, umul(x, x))
	{
		if (n & 1) umul(ans, x);
	}
	return ans;
}

namespace FFT
{
	const int mxn = 1 << 18;
	int N;
	int r[mxn];
	int w[mxn];
	
	void init(int n)
	{
		if (N == n) return;
		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));
			for (int i = 0; i < h; ++ i)
			{
				w[h + i] = i ? mul(w[h + i - 1], temp) : 1;
			}
		}
	}
	
	void dft(int a[], int n)
	{
		init(n);
		for (int i = 1; i < n - 1; ++ i)
		{
			if (i < r[i]) 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 = mul(a[i + h + j], w[h + j]);
					a[i + h + j] = add(a[i + j], mod - v);
					uadd(a[i + j], v);
				}
	}
	
	void idft(int a[], int n)
	{
		dft(a, n);
		reverse(a + 1, a + n);
		int iv = qpow(n, mod - 2);
		for (int i = 0; i < n; ++ i) umul(a[i], iv);
	}
}

struct Poly : vector <int>
{
	Poly() { clear(); }
	Poly(size_t n) { assign(n, 0); }
	Poly(vector <int> v) { clear(); for (int x : v) push_back(x); }
	Poly(initializer_list <int> v) { clear(); for (int x : v) push_back(x); }
	
	friend Poly operator + (const Poly &a, const Poly &b)
	{
		Poly c(max(a.size(), b.size()));
		for (int i = 0; i < (int) a.size(); ++ i) uadd(c[i], a[i]);
		for (int i = 0; i < (int) b.size(); ++ i) uadd(c[i], b[i]);
		return c;
	}
	
	friend Poly operator - (const Poly &a, const Poly &b)
	{
		Poly c(max(a.size(), b.size()));
		for (int i = 0; i < (int) a.size(); ++ i) uadd(c[i], a[i]);
		for (int i = 0; i < (int) b.size(); ++ i) uadd(c[i], mod - b[i]);
		return c;
	}
	
	friend 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() <= 32LL * sz)
		{
			for (int i = 0; i < (int) a.size(); ++ i)
				for (int j = 0; j < (int) b.size(); ++ j)
					uadd(c[i + j], mul(a[i], b[j]));
		}
		else
		{
			static int A[FFT::mxn], B[FFT::mxn];
			for (int i = 0; i < sz; ++ i) A[i] = i < (int) a.size() ? a[i] : 0;
			for (int i = 0; i < sz; ++ i) B[i] = i < (int) b.size() ? b[i] : 0;
			FFT::dft(A, sz);
			FFT::dft(B, sz);
			for (int i = 0; i < sz; ++ i) umul(A[i], B[i]);
			FFT::idft(A, sz);
			for (int i = 0; i < (int) c.size(); ++ i) c[i] = A[i];
		}
		return c;
	}
};

struct Func // kx + b
{
	Poly k, b;
	
	Func operator () (Func f) const
	{
		return {k * f.k, k * f.b + b};
	}
	Poly operator () (Poly f) const
	{
		return k * f + b;
	}
};

const int mxn = 2e5 + 5;

int n;
vector <int> adj[mxn];
int fa[mxn], sz[mxn], son[mxn];

void dfs(int u)
{
	sz[u] = 1, son[u] = 0;
	for (int v : adj[u]) if (v != fa[u])
	{
		fa[v] = u;
		dfs(v);
		sz[u] += sz[v];
		if (!son[u] || sz[v] > sz[son[u]]) son[u] = v;
	}
}

Poly solve(int);

Poly conq2(vector <int> &vec, int l, int r)
{
	if (l > r) return {1};
	if (l == r) return solve(vec[l]);
	int m = l;
	auto wei = [&] (int u)
	{
		return sz[u];
	};
	int Sl = 0, Sr = 0;
	for (int i = l; i <= r; ++ i) Sr += wei(vec[i]);
	while (Sl + wei(vec[m]) < Sr - wei(vec[m]))
	{
		Sl += wei(vec[m]), Sr -= wei(vec[m]);
		++ m;
	}
	return conq2(vec, l, m - 1) * conq2(vec, m, m) * conq2(vec, m + 1, r);
}

Func conq1(vector <int> &vec, int l, int r)
{
	if (l > r) return {{1}, {0}};
	if (l == r)
	{
		int u = vec[l];
		vector <int> lson;
		for (int v : adj[u]) if (v != fa[u] && v != son[u])
			lson.push_back(v);
		return {conq2(lson, 0, (int) lson.size() - 1), {0, 1}};
	}
	int m = l;
	auto wei = [&] (int u)
	{
		return sz[u] - sz[son[u]];
	};
	int Sl = 0, Sr = 0;
	for (int i = l; i <= r; ++ i) Sr += wei(vec[i]);
	while (Sl + wei(vec[m]) < Sr - wei(vec[m])) 
	{
		Sl += wei(vec[m]), Sr -= wei(vec[m]);
		++ m;
	}
	return conq1(vec, l, m - 1)(conq1(vec, m, m)(conq1(vec, m + 1, r)));
}

Poly solve(int u)
{
	vector <int> chain;
	for (int x = u; x; x = son[x]) chain.push_back(x);
	return conq1(chain, 0, (int) chain.size() - 1)((Poly){1});
}

int main()
{
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 2; i <= n; ++ i)
	{
		int p;
		cin >> p;
		adj[p].push_back(i);
	}
	dfs(1);
	Poly p = solve(1);
	for (int k = 1; k <= n; ++ k)
		cout << (k < (int) p.size() ? p[k] : 0) << "\n";
	return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘Poly operator*(const Poly&, const Poly&)’:
./Main.cpp:117:33: warning: comparison of integer expressions of different signedness: ‘long long unsigned int’ and ‘long long int’ [-Wsign-compare]
  117 |   if (1LL * a.size() * b.size() <= 32LL * sz)
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

ジャッジ結果