题解

Bubble Cup 9 - Finals [Online Mirror] A. Festival Organization

很显然，设$f_i$表示长度为$i$的满足条件的$01$串个数，那么有：

$$f _ i = f _ {i - 1} + f _ {i - 2},f _ 1 = 2, f _ 2 = 3$$
这只是将传统的$fib$序列左移了一下，反正答案是形如$solve(r)-solve(l-1)$的，因此将$l,r$分别加$2$当作$fib$来做就可以了，以下的$f_i$均表示下标从$1$开始的$fib$序列。
考虑我们现在要求的就是这样一个前缀和： $$\sum _ {i = 1} ^ {n} \binom{f _ i}{k}$$
看上去就好难的说，我们考虑一下$\binom{x}{k}$其实就是变量为$x$的一个$k$次多项式，因此我们可以求出每项前面的系数$a _ i$，然后我们的任务就变成了求出：
$$\sum _ {i = 0} ^ {k} \left( a _ i \cdot \sum _ {j = 1} ^ {n} f _ j ^ i \right)$$
所以我们现在的目的就是要求对于一个固定的$i$，$\sum _ {j = 1} ^ {n} f _ j ^ i$的值。
这个东西的计算方法我们考虑$fib$的通项：
$$f _ n = \frac{1}{\sqrt{5}}\cdot \left( \left(\frac{1 + \sqrt{5}}{2} \right) ^ n - \left(\frac{1 - \sqrt{5}}{2} \right) ^ n \right)$$
令$\varphi = \frac{1 + \sqrt{5}}{2}$，那么原式就是：
$$f_ n = \frac{\varphi ^ n - (-\varphi) ^ {-n}}{\sqrt{5}}，因为\frac{1 + \sqrt{5}}{2} \cdot \frac{1 - \sqrt{5}}{2} = -1$$
考虑$f _ j ^ i$怎么求，其实很简单，还记得复数是怎么表示的么，我们用$a+bi$来表示，那么这里我们可以用$a+b\cdot \sqrt{5}$来表示值，然后重定义加减乘除即可，这个就是很简单的了。
现在我们考虑怎么求$f _ j ^ i$的前缀和，根据二项式定理展开$f _ n$的分子，然后第$x$项形如：
$$\binom{i}{x}\varphi ^ {jx}(-(-\varphi)^{-j})^{i-x}$$
虽然有点小复杂， 但是可以看出$j$从$1\cdots n$这个东西构成了一个等比数列，简单讨论一下正负号然后等比数列求和即可。
注意公比为$1$要特判。