꼬마와 두 갈래 나무를 풀다

제목 전송문

제목의 대의.

집합\(S=\{c_1, c_2, c_3,..., c_m\}\) 을 제시하여 임의의\(t\in[1, m]\) 에 대해 두 갈래 트리가 모든 정점을 충족시키는 값이\(S\) 에 있고 값의 합이\(t\) 인지 확인합니다.

생각

우리는\(F\)를 정답의 생성 함수로 설정하고,\(G\)는 집합\(S\)의 생성 함수로 설정합니다.획득:
\[F=F^2G+1\]
\(F^2\)는 열거좌우 아들이고,\(G\)는 루트 노드이고,\(1\)는 빈 나무일 수 있기 때문이다.
지원:
\[F=\frac{1\pm\sqrt{1-4G}}{2G}\]
플러스를 찾으면\(G=0\) 0이 될 때 플러스가 무한하고 마이너스를 찾으면 로피다의 법칙으로 구할 수 있기 때문에 마이너스를 얻는다.우리는 다시 간단하게 할 수 있다.
\[F=\frac{2}{1+\sqrt{1-4G}}\]
그래서 우리는\(\Theta(m\logm)\)의 시간 복잡도 내에서 이 문제를 해결했다.

\(\text {Code}\)

#include 
using namespace std;

#define Int register int
#define inv2 499122177
#define ll long long
#define mod 998244353
#define MAXN 400005
#define Gi 3

int quick_pow (int a,int b){
	int res = 1;for (;b;b >>= 1,a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod;
	return res; 
}

int limit = 1,l,r[MAXN];

void NTT (int *a,int type){
	for (Int i = 0;i < limit;++ i) if (i < r[i]) swap (a[i],a[r[i]]);
	for (Int mid = 1;mid < limit;mid <<= 1){
		int Wn = quick_pow (Gi,(mod - 1) / (mid << 1));
		if (type == -1) Wn = quick_pow (Wn,mod - 2);
		for (Int R = mid << 1,j = 0;j < limit;j += R){
			for (Int k = 0,w = 1;k < mid;++ k,w = 1ll * w * Wn % mod)
			{
				int x = a[j + k],y = 1ll * w * a[j + k + mid] % mod;
				a[j + k] = (x + y) % mod,a[j + k + mid] = (x + mod - y) % mod;
			}
		}
	} 
	if (type == 1) return ;
	int Inv = quick_pow (limit,mod - 2);
	for (Int i = 0;i < limit;++ i) a[i] = 1ll * a[i] * Inv % mod;
}

int c[MAXN];

void Solve (int len,int *a,int *b){
	if (len == 1) return b[0] = quick_pow (a[0],mod - 2),void ();
	Solve ((len + 1) >> 1,a,b);
	limit = 1,l = 0;
	while (limit < (len << 1)) limit <<= 1,l ++;
	for (Int i = 0;i < limit;++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
	for (Int i = 0;i < len;++ i) c[i] = a[i];
	for (Int i = len;i < limit;++ i) c[i] = 0;
	NTT (c,1);NTT (b,1);
	for (Int i = 0;i < limit;++ i) b[i] = 1ll * b[i] * (2 + mod - 1ll * c[i] * b[i] % mod) % mod;
	NTT (b,-1);
	for (Int i = len;i < limit;++ i) b[i] = 0;
}

int C[MAXN],D[MAXN];

void Sqrt (int *a,int *b,int n){
	if (n == 1) return b[0] = a[0],void ();
	Sqrt (a,b,n >> 1);
	for (Int i = 0;i < n;++ i) C[i] = a[i];
	Solve (n,b,D);
	NTT (C,1);NTT (D,1);
	for (Int i = 0;i < limit;++ i) D[i] = 1ll * D[i] * C[i] % mod;
	NTT (D,-1);
	for (Int i = 0;i < limit;++ i) b[i] = 1ll * (b[i] + D[i]) % mod * inv2 % mod,C[i] = D[i] = 0; 
}

int read (){
	int x = 0;char c = getchar();int f = 1;
	while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}
	while (c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + c - '0';c = getchar();}
	return x * f;
}

void write (int x){
	if (x < 0){x = -x;putchar ('-');}
	if (x > 9) write (x / 10);
	putchar (x % 10 + '0');
}

int n,m,G[MAXN],F[MAXN],T[MAXN];

signed main(){
	n = read (),m = read ();
	for (Int i = 1,w;i <= n;++ i){
		w = read ();
		if (w <= m) F[w] ++;
	}
	while (limit <= m) limit <<= 1,l ++;
	for (Int i = 0;i < limit;++ i) F[i] = (i == 0) ? 1 + mod - 4 * F[i] : mod - 4 * F[i];
	Sqrt (F,T,limit),T[0] ++,Solve (limit,T,G);
	for (Int i = 1;i <= m;++i) write (2 * G[i] % mod),putchar ('
');
	return 0;
}