新手表示满脑子只有 \(DP\) ……
设一个憨批数组 \(s\) ，值只有 \(0/1\) 第 \(i\) 位表示 \(i\) 这个数字是否合法
首先找到 \(dp\) 方程： \(f_n=\sum{s_i\sum{f_{n-j-i}f_{j}}}\)
同时知道 \(f_0=1\)
嗯，看起来很好吃
然后我们设 \(f\) 的生成函数为 \(F(x)=\sum{f_ix^i}\)
设 \(s\) 的生成函数是 \(G(x)=\sum{s_ix^i}\)
我们规定常数项为 \(0\) ,因为原题中给定的合法数大于 \(0\) (\(\forall i,s_i>0\))
那么每一项就是

\[F_i=\sum\limits_{j=1}^{j<=i}{s_j\sum\limits_{k=0}^{k<=i-j}{F_{i-j-k}*F_{k}}} \]

\[F=1+G*F^2 \]

然后考虑化简，题解有人对直接求根表示质疑，我觉得他的证明非常好，值得学习

\[GF=F^2G^2+G \]

\[0=F^2G^2-GF+G \]

\[0=(FG+\frac{1}{2})^2-\frac{1}{4}+G \]

\[\frac{1}{4}-G=(GF-\frac{1}{2})^2 \]

\[1-4G=4(GF-\frac{1}{2}) \]

然后因为左式的常数项不是 \(0\) 了，我们可以开根

\[-\sqrt[2]{1-4G}=2(GF-\frac{1}{2}) \]

考虑到我们还有个 \(GF\) ，这个小家伙的常数项必为 \(0\) (\(GF_0=G_0*F_0\))
如果我们选择了正，那么左式的常数项就不为 \(0\) 所以我们必须得选择取负

\[\frac{1-\sqrt[2]{1-4G}}{2}=GF \]

初一数学，上下同乘 \(1+\sqrt[2]{1-4G}\) ，于是原式就被化简成了

\[F=\frac{2}{1+\sqrt[2]{1-4G}} \]

是的是的我跳步了
然后让我们冲！