题解：P16822 [蓝桥杯 2026 国 Python B] 零段积分

· · 题解

世界机器还是太厉害了，来点唐唐做法。

设 x=\dfrac pq，y=1-x。

容易发现 l_il_{i+1} 的组合意义就是从相邻的连续 0 段中各选出一个 0 的方案数。根据期望的线性性，我们相当于要求

\sum_{1\leq i<j\leq n}P(i,j)

其中 P(i,j) 表示 i,j 处于相邻 0 段的概率。

设 len=j-i+1，则 [i,j] 一定是形如 0^a1^b0^c。考虑到 a+c=len-b，不难得出

P(i,j)=\sum_{b=1}^{len-3}(len-b-1)x^by^{len-b}

上式显然只跟 len 有关，不妨设为 f_{len}，则答案为

\sum_{len=3}^n(n-len+1)f_{len}

考虑 \mathcal{O}(n) 计算 f_{len}。不难想到递推，设

g_{len}=\sum_{b=1}^{len-2}x^by^{len-b}

套路地拆出来最后一项，容易得到递推式：

\begin{align*} f_{len}&=x^{len-2}y^2+y(f_{len-1}+g_{len-1})\\ g_{len}&=x^{len-2}y^2+yg_{len}-1 \end{align*}

递推的同时算出 x^{len-2}y^2 即可做到 \mathcal{O}(n)。可以通过本题。

进一步优化，考虑矩阵快速幂加速。容易想到要把 f,g,x^{len-1} 都加到矩阵里。至于 (n-len+1)f_{len}，套路地转化成二维前缀和：

\sum_{len=3}^n(n-len+1)f_{len}=\sum_{i=3}^n\sum_{j=3}^i f_j

于是设

\begin{align*} A_i&=\sum_{len=3}^i f_{len}\\ B_i&=\sum_{len=3}^i A_{len} \end{align*}

将 A,B 也加入矩阵中即可。

简单推一下矩阵。初始向量为

V=\begin{bmatrix} f_3\\ g_3\\ x^2\\ f_3\\ f_3 \end{bmatrix}

转移矩阵为

T=\begin{bmatrix} y & y & y^2 & 0 & 0\\ 0 & y & y^2 & 0 & 0\\ 0 & 0 & x & 0 & 0\\ y & y & y^2 & 1 & 0\\ y & y & y^2 & 1 & 1 \end{bmatrix}

直接计算 T^{n-3}V 即可。时间复杂度为 \mathcal{O}(\log{n})。

:::success[主要代码]

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
const int mod = 1e9 + 7;

template<typename T> T lowbit(T x) { return x & -x; }
template<typename T> void chkMin(T &x, T y) { x = y < x ? y : x; }
template<typename T> void chkMax(T &x, T y) { x = x < y ? y : x; }
template<typename T> T add(T x, T y) { return (x += y) >= mod ? x - mod : x; }
template<typename T> T sub(T x, T y) { return (x -= y) < 0 ? x + mod : x; }
template<typename T> void cadd(T &x, T y) { (x += y) >= mod ? (x -= mod) : x; }
template<typename T> void csub(T &x, T y) { (x -= y) < 0 ? (x += mod) : x; }

int n, p, q;

template<int N, int M>
struct Matrix {
    array<array<int, M>, N> a;
    Matrix() {
        for (int i = 0; i < N; ++i) a[i].fill(0);
    }
    int &operator()(int i, int j) {
        return a[i][j];
    }
    int operator()(int i, int j) const {
        return a[i][j];
    }
    template<int P>
    friend Matrix<N, P> operator*(const Matrix<N, M> &lhs, const Matrix<M, P> &rhs) {
        Matrix<N, P> res;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < P; ++j) {
                int s = 0;
                for (int k = 0; k < M; ++k) cadd<int>(s, (ull)lhs(i, k) * rhs(k, j) % mod);
                res(i, j) = s;
            }
        }
        return res;
    }
};

template<int N>
Matrix<N, N> idMat() {
    Matrix<N, N> res;
    for (int i = 0; i < N; ++i) res(i, i) = 1;
    return res;
}

template<int N>
Matrix<N, N> qpow(Matrix<N, N> a, int b) {
    Matrix<N, N> res = idMat<N>();
    for (; b; b >>= 1) {
        if (b & 1) res = res * a;
        a = a * a;
    }
    return res;
}

int qpow(int a, int b) {
    int res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (ll)res * a % mod;
        a = (ll)a * a % mod;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> p >> q;
    int x = (ull)p * qpow(q, mod - 2) % mod, y = sub(1, x);
    Matrix<5, 1> V;
    V(0, 0) = V(1, 0) = V(3, 0) = V(4, 0) = (ull)x * y % mod * y % mod;
    V(2, 0) = (ull)x * x % mod;
    Matrix<5, 5> T;
    T(0, 0) = T(0, 1) = T(1, 1) = T(3, 0) = T(3, 1) = T(4, 0) = T(4, 1) = y;
    T(0, 2) = T(1, 2) = T(3, 2) = T(4, 2) = (ull)y * y % mod;
    T(2, 2) = x;
    T(3, 3) = T(4, 3) = T(4, 4) = 1;
    cout << (n < 3 ? 0 : (qpow(T, n - 3) * V)(4, 0));
    return 0;
}

:::