Description：

求出恰好有 $s$ 个叶子并且每个点的儿子个数 $\in S$ 的多叉树的方案数。

$1\leqslant n\leqslant 10^5$

Solution：

设 $s_i=[i\in S]$ 的生成函数为 $S(x)$ ，答案的生成函数为 $F(x)$ ，那么有： $$ F(x)=x+\sum_{i\in S}F^i(x) $$ 后面是一个关于 $F$ 的多项式，也就是多项式的复合，考虑拉格朗日反演： $$ G(x)=x-\sum_{i\in S}x^i\Rightarrow G(F(x))=x $$ 现在已知 $G$ 要求 $F$ 可以拉格朗日反演。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,s;

#define MAXN 400010

#define P 950009857 

#define G 7 

int a[MAXN],b[MAXN],c[MAXN];

#define I inline

#define R register

int rev[MAXN];

int ww[MAXN << 1],*g = ww + MAXN;

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;a = 1ll * a * a % P,b = b >> 1)if(b & 1)res = 1ll * res * a % P;

	return res;

}

int inver(int a){return power(a,P - 2);}

int init(int n)

{

	int l = 0,len = 1;

	for(;len <= n;len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(G,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % P;

	return len;

}

void NTT(int f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		int wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			int w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				int u = f[k],t = 1ll * w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = 1ll * w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		int ni = power(l,P - 2);

		for(int i = 0;i < l;++i)f[i] = 1ll * f[i] * ni % P;

	}

	return;

}

int invtmp[MAXN];

void calc_inv(int deg,int a[],int b[])

{

	if(deg == 1)

	{

		b[0] = power(a[0],P - 2);

		return;

	}

	calc_inv(((deg + 1) >> 1),a,b);

	int len = init(deg * 2);

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

	for(int i = deg;i < len;++i)invtmp[i] = 0;

	NTT(invtmp,len,1);NTT(b,len,1);

	for(int i = 0;i < len;++i)

	{

		b[i] = (2ll * b[i] - 1ll * invtmp[i] * b[i] % P * b[i] % P + P) % P;

	}

	NTT(b,len,-1);

	for(int i = deg;i < len;++i)b[i] = 0;

	return;

}

int lnt[MAXN];

void poly_ln(int deg,int a[],int b[])

{

	calc_inv(deg,a,b);

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

	for(int i = 0;i < deg;++i)lnt[i] = 1ll * (i + 1) * lnt[i + 1] % P;

	int l = init(deg * 2);

	NTT(lnt,l,1);NTT(b,l,1);

	for(int i = 0;i < l;++i)lnt[i] = 1ll * lnt[i] * b[i] % P;

	NTT(lnt,l,-1);

	for(int i = deg;i > 0;--i)lnt[i] = 1ll * inver(i) * lnt[i - 1] % P;lnt[0] = 0;

	for(int i = 0;i < deg;++i)b[i] = lnt[i];

	for(int i = deg;i < l;++i)b[i] = 0;

	for(int i = 0;i < l;++i)lnt[i] = 0; 

	return;

}

int expt[MAXN];

void poly_exp(int deg,int a[],int b[])

{

	if(deg == 1)

	{

		b[0] = 1;

		return; 

	}

	poly_exp((deg + 1) >> 1,a,b);

	poly_ln(deg,b,expt);

	for(int i = 0;i < deg;++i)expt[i] = (a[i] - expt[i] + P) % P;

	expt[0] = (expt[0] + 1) % P;

	int l = init(deg * 2);

	NTT(expt,l,1);NTT(b,l,1);

	for(int i = 0;i < l;++i)expt[i] = 1ll * expt[i] * b[i] % P;

	NTT(expt,l,-1);

	for(int i = 0;i < deg;++i)b[i] = expt[i];

	for(int i = deg;i < l;++i)b[i] = 0;

	for(int i = 0;i < l;++i)expt[i] = 0;

	return;

}

int main()

{

	scanf("%d%d",&s,&n);

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

	{

		int x;

		scanf("%d",&x);

		a[x] = P - 1;

	}

	a[1] = (a[1] + 1) % P;

	for(int i = 0;i < s;++i)a[i] = a[i + 1];

	poly_ln(s,a,b);

	for(int i = 0;i < s;++i)b[i] = 1ll * b[i] * (P - s) % P;

	poly_exp(s,b,c);

	printf("%d ",1ll * c[s - 1] * inver(s) % P);

	return 0;

}