牡牛和牝牛
考虑 DP。$f(i)$ 表示到第 $i$ 只牛,最后一只是公牛的方案数。转移显然有:
$$ f(i)=\sum_{j=0}^{i-k-1} f(j) $$
前缀和优化一下,记
$$ s(i)=\sum_{j=0}^{i} f(j) $$
最终答案就是 $s(n)$。代码。
方程的解
令 $x=x^x \bmod 1000$,由隔板法可得答案是 $C_{x-1}^{k-1}$。
序列统计
全场最难题。
已知原数组 $a$ 长度为 $k\in [1,n]$。让 a[i]-=L
,可得约束条件
$$ 0\le a_1\le a_2\le \cdots \le a_k\le R-L $$
考虑差分。差分数组 $x_i=a_i-a_{i-1},x_1=a_1,x_i\ge 0$,可以得到 $\sum_{i=1}^k x_i\le R-L$。
令 $y_i=x_i+1$,有 $\sum_{i=1}^k y_i\le R-L+k$。
这是一个经典的隔板法问题,答案是 $C_{R-L+k}^k$。我们还是没法枚举每一个 $k$。考虑推式子。令 $m=R-L$。
$$ \begin{align*} \sum_{k=1}^n C_{R-L+k}^k&=\sum_{k=1}^n C_{m+k}^k\\ &=C_{m+1}^1+C_{m+2}^2+\cdots+C_{m+n}^n\\ &=C_{m+1}^m+C_{m+2}^m+\cdots+C_{m+n}^m\\ &=C_{m+1}^m+C_{m+2}^m+\cdots+C_{m+n}^m\\ &=C_{m+1}^{m+1}+C_{m+1}^m+C_{m+2}^m+\cdots+C_{m+n}^m-C_{m+1}^{m+1}\\ &=C_{m+2}^{m+1}+C_{m+2}^m+\cdots+C_{m+n}^m-C_{m+1}^{m+1}\\ &=C_{m+3}^{m+1}+\cdots+C_{m+n}^m-C_{m+1}^{m+1}\\ &=\cdots\\ &=C_{m+n}^{m+1}+C_{m+n}^m-C_{m+1}^{m+1}\\ &=C_{m+n+1}^{m+1}-1\\ \end{align*} $$
$C_{m+n+1}^{m+1}$ 可以使用 Lucas 定理快速计算。代码。