首先考虑求出长度为 \(i\) 的合法串的个数。
很明显可以想到用 dp 解。
设 \(f_{i,0/1}\) 为长度为 \(i\) 最后一位为 \(0/1\) 的合法串个数。
可以很容易想到转移方程：
\(f_{i,0}=f_{i-1,0}\)
\(f_{i,1}=f_{i-1,1}+f_{i-1,0}\)
第一个方程代入第二个方程：
\(f_{i,1}=f_{i-1,1}+f_{i-2,1}\)
答案为 \(f_{i,0}+f{i,1}\)。
即为 \(f_{i-1,1}+f_{i,1}=f_{i+1,1}\)
那么可以省掉一位，转移方程重新改为：
\(f_i=f_{i-1}+f_{i-2}\)
这个也同样是斐波那契的通项式，由于 \(f_1=2\)，所以是斐波那契整体往左移动了两位。
我们知道斐波那契数列通项式为：
\(F_i=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^i-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^i\)
这样明显是会 T 的，而且还要求 \(\sum_{i=l}^r\binom{f_i}{k}\)，所以没法直接用斐波那契通项式求解。
首先拆开 \(\binom{f_i}{k}\)。
\(\binom{f_i}{k}=\frac{f_i^{\underline{k}}}{k!}\)。
\(f_i^{\underline{k}}\) 为下降次幂，代表 \(f_i\times (f_i-1)\times ...\times(f_i-k+1)\)。
下降次幂可以用第一类斯特林数拆开，为：
\(x^{\underline{k}}=\sum_{i=1}^k(-1)^{k-i}\times \left[^k_i\right]\times x^i\)。
\(\left[^x_y\right]\) 代表第一类斯特林数，将 \(x\) 个不同的数划分成 \(y\) 个相同的圆排列。可以递推求解，接下来用 \(s_{x,y}\) 代替第一类斯特林数：
\(s_{x,y}=s_{x-1,y-1}+s_{x-1,y}\times(x-1)\)。
左边的组合意义为 \(x\) 个数有序的选了 \(k\) 个的方案数。
右边即是将 \(k\) 个数划分成 \(i\) 个圆排列，再将有标号的圆排列放入 \(x\) 个有标号的盒子中，允许空，再做容斥。那么最后右边会得到 \(k\) 个大小为 \(1\) 的有标号的圆排列放入 \(x\) 个盒子中。
很明显左右等价，等式成立。
那么原式可以正常转化为：
\(\sum_{i=l}^r\frac{\sum_{j=0}^k(-1)^{k-j}\times s_{k,j}\times f_i^j}{k!}\)
提出 \(\frac{1}{k!}\)，原式为：
\(\frac{1}{k!}\sum_{i=l}^r\sum_{j=0}^k(-1)^{k-j}\times s_{k,j}\times f_i^j\)。
设 \(A=\frac{1}{\sqrt{5}},B=-A,C=\frac{1+\sqrt{5}}{2},D=\frac{1-\sqrt{5}}{2}\)。
代入得：
\(\frac{1}{k!}\sum_{i=l}^r\sum_{j=0}^k(-1)^{k-j}\times s_{k,j}\times (AC^i+BD^i)^j\)。
牛顿二项式定理拆开最后一项：
\(\frac{1}{k!}\sum_{i=l}^r\sum_{j=0}^k(-1)^{k-j}\times s_{k,j}\times \sum_{p=0}^j(AC^i)^p(BD^i)^{p-j}\)。
\(A,B\) 与 \(i\) 无关，提出。
\(\frac{1}{k!}\sum_{j=0}^k(-1)^{k-j}\times s_{k,j}\times \sum_{p=0}^jA^pB^{j-p}\sum_{i=l}^r(C^pD^{p-j})^i\)。
前面 \(k^2\) 枚举就可以出来了，后面 \(C^pD^{p-j}\) 也只有 \(k^2\) 种可能。
那现在等价于就是求 \(g(x)=\sum_{n=0}^{r}x^n\)，再用前缀和相减。
这玩意就是等比数列。正常求就完事了。
时间复杂度：\(O(k^2)\)。
标签：frac,Festival,题解,sum,sqrt,times,CF717A,那契,underline From： https://www.cnblogs.com/gmtfff/p/cf717a.html