题目大意
一个合法的串定义为:长度在 $[l,r]$ 之间,且只含 0
,1
,并且不存在连续 $2$ 个或更多的 $0$。
现在要选出 $k$ 个长度相同的合法的串,问有几种选法,答案模 $10^9+7$。
$ 1 \leq k \leq 200$,$1 \leq l \leq r \leq 10^{18}$
题目分析
显而易见的我们要求的是一个形如 $ \sum_{l+2}^{r+2} \binom{f_i}{k}$的东西,其中 $f_i$表示斐波那契数列的第$i$项
我们把上式转化成求$ \sum_{i=1}^{n} \binom{f_i}{k}$,那么我们可以开始推式子了
$$
\sum_{i=1}^n \binom {f_i}{k}
$$
$$
= \frac{1}{k!} \sum_{i=1}^n \sum_{j=1}^k (f_i - j + 1)
$$
$$
= \frac{1}{k!} \sum_{i=1}^n \sum_{j=1}^k (-1)^{k-j} \begin{bmatrix}k \\ j\end{bmatrix} f_i^j
$$
这里用的是下降幂多项式转普通多项式的方法,$\begin{bmatrix}k \\ j\end{bmatrix}$是第一类斯特林数
$$
= \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} \begin{bmatrix}k \\ j\end{bmatrix} \sum_{i=1}^n f_i^j
$$
$$
= \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} \begin{bmatrix}k \\ j\end{bmatrix} \sum_{i=1}^n (\frac{1}{\sqrt 5}(\phi^i - \hat{\phi}^i))^j
$$
$$
= \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} \begin{bmatrix}k \\ j\end{bmatrix} (\frac{1}{\sqrt 5})^j \sum_{i=1}^n (\phi^i - \hat{\phi}^i)^j
$$
$$
= \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} \begin{bmatrix}k \\ j\end{bmatrix} (\frac{1}{\sqrt 5})^j \sum_{i=1}^n \sum_{l=0}^j (-1)^l \binom{j}{l} \phi^{li} \hat{\phi}^{(j-l)i}
$$
$$
= \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} \begin{bmatrix}k \\ j\end{bmatrix} (\frac{1}{\sqrt 5})^j \sum_{l=1}^j (-1)^l \binom{j}{l} \sum_{i=1}^n (\phi^{l} \hat{\phi}^{(j-l)})^i
$$
$$
= \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} \begin{bmatrix}k \\ j\end{bmatrix} (\frac{1}{\sqrt 5})^j \sum_{l=1}^j (-1)^l \binom{j}{l} \frac{\phi^{l} \hat{\phi}^{(j-l)}({1-\phi^{l} \hat{\phi}^{(j-l)})^n}}{1-\phi^{l}\hat{\phi}^{(j-l)}}
$$
大概就是这样一个式子,接下来就可以在 $O(k^2)$的时间内计算这个东西了
但是我们发现,浮点数显然无法承担这么复杂的计算任务,怎么处理 $\phi$和$\hat{\phi}$呢?
类似于 $a + bi$的形式,我们搞一个$a+b\sqrt{5}$出来,接下来就可以用这个数域处理上面的式子了
最后会附上草稿纸的原图,如果发现有和上面不一样的请联系我,谢谢!
代码
1 | #include <bits/stdc++.h> |