[BZOJ3625][Codeforces Round #250]小朋友和二叉树多项式开根+求逆

https://www.lydsy.com/JudgeOnline/problem.php?id=3625

愉快地列式子。设\(F[i]\)表示权值为\(i\) 的子树的方案数，\(A[i]\)为\(i\)在不在集合中。

\[F[n]=\sum_{i=0}^n \sum_{j=0}^{n-i}F[i]\cdot F[j]\cdot A[n-i-j]
\]

初始状态\(F[0]=1\)。

我们把\(F,A\)看成多项式。

\[F(x)-1=F^2(x)\cdot A(x)\\
A(x)\cdot F^2(x)-F(x)+1=0\\
F(x)=\frac{1\pm\sqrt{1-4A(x)}}{2A(x)}
\]

因为\(A[0]=0\)而\(F[0]=1\)，如果取\(+\)号，末位会不符，舍出。因此只能取\(-\)。

这样

\[\begin{align*}
F(x)&=\frac{1-\sqrt{1-4A(x)}}{2A(x)}\\
&=\frac{(1-\sqrt{1-4A(x)})(1+\sqrt{1-4A(x)})}{2A(x)(1+\sqrt{1-4A(x)})}\\
&=\frac{4A(x)}{2A(x)(1+\sqrt{1-4A(x)})}\\
&=\frac{2}{1+\sqrt{1-4A(x)}}
\end{align*}
\]

这样就变成多项式开根+求逆的板子了。

(刚开始转码风，可能有些地方不太自然，也有可能有些地方仍然保留着就码风没有注意)

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

#define isbreak dbg("*")

template<typename A, typename B> inline char SMAX(A &a, const B &b) {return a < b ? a = b , 1 : 0;}

template<typename A, typename B> inline char SMIN(A &a, const B &b) {return b < a ? a = b , 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I>

inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

const int N = 4e5 + 7;

const int P = 998244353;

const int G = 3;

const int Gi = 332748118;

const int Inv2 = 499122177;

int n, m, x, a[N];

inline void SADD(int &x, int y) {x += y;x >= P ? x -= P : 0;}

inline int SMOD(int x) {return x >= P ? x - P : x;}

inline int fpow(int x,int y) {

	int ans = 1;

	for (; y; y >>= 1, x = (ll)x * x % P) if (y & 1) ans = (ll)ans * x % P;

	return ans;

}

namespace DFT {

	int A[N], B[N], C[N];

	inline void NTT(int *a, int n, int f) {

		for (int i = 0, j = 0; i < n; ++i) {

			if (i > j) std::swap(a[i], a[j]);

			for (int l = n >> 1; (j ^= l) < l; l >>= 1);

		}

		for (int i = 1; i < n; i <<= 1) {

			int w = fpow(f > 0 ? G : Gi, (P - 1) / (i << 1));

			for (int j = 0; j < n; j += i << 1)

				for (int k = 0, e = 1; k < i; ++k, e = (ll)e * w % P){

					int x = a[j + k], y = (ll)e * a[i + j + k] % P;

					a[j + k] = SMOD(x + y); a[i + j + k] = SMOD(x + P - y);

				}

		}

		if (f < 0) for (int i = 0, p = fpow(n, P - 2); i < n; ++i) a[i] = (ll)a[i] * p % P;

	}

	namespace Inv {

		int A[N], B[N];

		inline void GetInv(int *a, int n, int *b) {

			memset(B, 0, sizeof(B)); B[0] = fpow(a[0], P - 2);

			for (int deg = 2; deg < (n << 1); deg <<= 1) {

				int L = deg << 1;

				for (int i = 0; i < deg; ++i) A[i] = a[i];

				for (int i = deg; i < L; ++i) A[i] = 0;

				NTT(A, L, 1); NTT(B, L, 1);

				for (int i = 0; i < L; ++i) B[i] = (ll)B[i] * (2 + P - (ll)B[i] * A[i] % P) % P;

				NTT(B, L, -1);

				for (int i = deg; i < L; ++i) B[i] = 0;

			}

			for (int i = 0; i < n; ++i) b[i] = B[i];

		}

	} using Inv::GetInv;

	inline void GetSqrt(int *a, int n, int *b) {

		B[0] = 1;

		for (int deg = 2; deg < (n << 1); deg <<= 1) {

			int L = deg << 1;

			for (int i = 0; i < deg; ++i) A[i] = a[i];

			for (int i = deg; i < L; ++i) A[i] = 0;

			GetInv(B, deg, C);

			NTT(A, L, 1); NTT(C, L, 1);

			for (int i = 0; i < L; ++i) C[i] = (ll)A[i] * C[i] % P;

			NTT(C, L, -1);

			for (int i = 0; i < L; ++i) B[i] = (ll)(B[i] + C[i]) * Inv2 % P;

			for (int i = deg; i < L; ++i) B[i] = 0;

		}

		for (int i = 0; i < n; ++i) b[i] = B[i];

	}

}

using DFT::GetInv;

using DFT::GetSqrt;

int main() {

	#ifdef hzhkk

	freopen("hkk.in", "r", stdin);

	#endif

	read(n), read(m);

	for (int i = 1; i <= n; ++i) read(x), a[x] = 1;

	for (int i = 1; i <= m; ++i) if (a[i]) a[i] = P - SMOD(SMOD(a[i] << 1) << 1);

	a[0] = 1;

	GetSqrt(a, m + 1, a);  SADD(a[0], 1);

	GetInv(a, m + 1, a);

	for (int i = 1; i <= m; ++i) printf("%d\n", SMOD(a[i] << 1));

}

巴特西

[BZOJ3625][Codeforces Round #250]小朋友和二叉树多项式开根+求逆

最新文章

热门文章

巴特西

[BZOJ3625][Codeforces Round #250]小朋友和二叉树 多项式开根+求逆

最新文章

热门文章

[BZOJ3625][Codeforces Round #250]小朋友和二叉树多项式开根+求逆