BZOJ 3684 大朋友和多叉树

Description

我们的大朋友很喜欢计算机科学，而且尤其喜欢多叉树。对于一棵带有正整数点权的有根多叉树，如果它满足这样的性质，我们的大朋友就会将其称作神犇的：点权为1的结点是叶子结点；对于任一点权大于1的结点u，u的孩子数目deg[u]属于集合D，且u的点权等于这些孩子结点的点权之和。

给出一个整数s，你能求出根节点权值为s的神犇多叉树的个数吗？请参照样例以更好的理解什么样的两棵多叉树会被视为不同的。

我们只需要知道答案关于\(950009857\)（\(453*2^{21}+1\)，一个质数）取模后的值。

Input

第一行有\(2\)个整数\(s,m\)。

第二行有\(m\)个互异的整数，\(d[1],d[2],…,d[m]\)，为集合\(D\)中的元素。

Output

输出一行仅一个整数，表示答案模\(950009857\)的值。

Sample Input

4 2

2 3

Sample Output

10

---

前置知识：

\(\text{Lagrange}\)反演（金策的论文中有讲）：

若两个没有常数项的函数\(f(x)\)和\(g(x)\)满足：

\[ f(g(x))=x \]

（也称这两个函数互为复合逆。）

我们就有：

\[ [x^n]g(x)=\frac{1}{n}[w^{n-1}](\frac{w}{f(w)})^n \]

---

设\(T(x)\)为答案的生成函数。

我们有：

\[ T(x)=x+\sum_{i\in D}{T(x)}^i \]

加上一个\(x\)是因为要考虑\(x\)为叶子的情况。

移项：

\[ T(x)-\sum_{i\in D}{T(x)}^i=x \]

设：

\[ f(x)=x-\sum_{i\in D}x^i \]

则：

\[ f(T(x))=x\\ \Rightarrow [x^n]T(x)=\frac{1}{n}[w^{n-1}](\frac{w}{f(w)})^n \]

\(\frac{w}{f(w)}\)上下约掉\(w\)后发现相当于将\(f(w)\)的每一项向左平移再求逆。

然后：

\[ f(x)^k=\exp(k\ln(f(x))) \]

代码：

#include
    
     #define ll long long#define N 100005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}const ll mod=950009857;ll ksm(ll t,ll x) {    ll ans=1;    for(;x;x>>=1,t=t*t%mod)        if(x&1) ans=ans*t%mod;    return ans;}ll NTT(ll *a,int d,int flag) {    static int rev[N<<2];    static int G=7;    int n=1<
     
      >1]>>1)|((i&1)<
      
       >1;        ll w=flag==1?ksm(G,(mod-1)/len):ksm(G,mod-1-(mod-1)/len);        for(int i=0;i