题解：P16822 [蓝桥杯 2026 国 Python B] 零段积分
WorldMachine
·
·
题解
你告诉我你在手推什么玩意。
下面设 p=\dfrac PQ 为变 1 的概率，q=1-p 为变 0 的概率。
考虑组合意义，就是说数对 (x,y) 的数量，满足 A_x=A_y=0，且 [x,y] 之间恰有一个 1 连续段。
设 x 右边（不含 x）有 a 个连续的 0，y 左边（不含 y）有 b 个连续的 0，中间的 1 连续段长度为 k，则贡献为 (n-a-b-k-1)q^{a+b+2}p^k。
枚举 i=a+b，求和项都只与 i 有关，令 m=n-k-2，原式化为：
\sum_{i=0}^{n-2-k}(i+1)(n-i-k-1)q^{i+2}p^k=q^2p^k\sum_{i=0}^m(i+1)(m+1-i)q^i
答案为：
\sum_{m=0}^{n-3}q^2p^{n-m-2}\left((m+1)\sum_{i=0}^m(i+1)q^i-\sum_{i=0}^mi(i+1)q^i\right)
对于括号内的两个求和号，预处理 f_m 和 g_m 两个前缀和即可做到 \mathcal O(n) 的复杂度，考虑进一步优化。
设 F_n(q)=\displaystyle\sum_{i=0}^nq^i=\dfrac{q^{n+1}-1}{q-1}，则：
\begin{aligned}
F_n'(q)&=\displaystyle\sum_{i=0}^{n-1}(i+1)q^i\\&=\dfrac{(n+1)q^n(q-1)-(q^{n+1}-1)}{(q-1)^2}\\
&=\dfrac{nq^{n+1}-(n+1)q^n+1}{(q-1)^2}
\end{aligned}
因此有：
f_m=F_{n+1}'(q)=\dfrac{(m+1)q^{m+2}-(m+2)q^{m+1}+1}{(q-1)^2}
再考虑 g_m，有：
\begin{aligned}
F_n''(q)&=\sum_{i=0}^{n-2}(i+1)(i+2)q^i=\sum_{i=0}^{n-1}i(i+1)q^{i-1}\\
&=\dfrac{n(n+1)q^{n-1}(q-1)^3-(nq^{n+1}-(n+1)q^n+1)(2q-2)}{(q-1)^4}\\
&=\dfrac{n(n-1)q^{n+1}-2(n-1)(n+1)q^n+n(n+1)q^{n-1}-2}{(q-1)^3}
\end{aligned}
因此有：
g_m=qF_{m+1}''(q)=\dfrac{m(m+1)q^{m+3}-2m(m+2)q^{m+2}+(m+1)(m+2)q^{m+1}-2q}{(q-1)^3}
那么答案即为：
\begin{aligned}
\fbox{answer}&=\dfrac{q^2p^{n-2}}{(q-1)^3}\sum_{m=0}^{n-3}p^{-m}\left((m+1)(q-1)((m+1)q^{m+2}-(m+2)q^{m+1}+1)-(m(m+1)q^{m+3}-2m(m+2)q^{m+2}+(m+1)(m+2)q^{m+1}-2q)\right)\\
&=\dfrac{q^2p^{n-2}}{(q-1)^3}\sum_{m=0}^{n-3}p^{-m}(((m+1)q^3-(m+3)q^2)q^m+(m+3)q-(m+1))\\
&=\dfrac{q^2p^{n-2}}{(q-1)^3}\left(\sum_{m=0}^{n-3}((m+1)q^3-(m+3)q^2)\left(\frac{q}{p}\right)^m+\sum_{m=0}^{n-3}((m+3)q-(m+1))\left(\frac{1}{p}\right)^m\right)
\end{aligned}
使用下面的公式：
\sum_{i=0}^n(ai+b)q^i=\dfrac{(b+an)q^{n+2}-(b+a(n+1))q^{n+1}+(a-b)q+b}{(q-1)^2}
于是得到答案为：
\fbox{answer}=\dfrac{q^2p^{n-2}}{(q-1)^3}\left(\dfrac{p^2q^2X}{(p-q)^2}+\dfrac{p^2Y}{(p-1)^2}\right)
其中：
\begin{aligned}
X&=(q-3)+\dfrac{2q}{p}-(q(n-1)-(n+1))\left(\dfrac qp\right)^{n-2}+(q(n-2)-n)\left(\dfrac qp\right)^{n-1}\\
Y&=(3q-1)-\dfrac{2q}p-(q(n+1)-(n-1))\left(\dfrac 1p\right)^{n-2}+(qn-(n-2))\left(\dfrac 1p\right)^{n-1}
\end{aligned}
还有个问题，如果 p=q 的话含 X 的那一坨会炸，这时退化为普通的等差数列求和：
\fbox{sum}=(n-2)q^2\left(\dfrac{(n-3)(q-1)}{2}+(q-3)\right)
不过含 Y 的那一坨没影响，因为 p=1 的情况一开始判掉就好了。
时间复杂度为 \mathcal O(\log n)，就应该整个 T=10^6 组数据然后 n 开 10^9 哇。