题解：CF868G El Toll Caves

· · 题解

还在 DP？提供一个直接冲的做法！

首先显然策略是转着每次选 k 个，考虑 \mathbb E(X)=\sum_k\mathbb P(X>k)，而 \mathbb P(X>k) 就是选 k 次还没击中答案的概率。显然位置 i 有宝藏、c 轮过后还没击中的概率是 (\frac12)^{\lfloor\frac{kc-i}n\rfloor+1}，那么可以写出答案的表达式：

\mathrm{ans}=\dfrac1n\sum_{i=1}^n\sum_{c\ge0}\left(\dfrac12\right)^{\lfloor\frac{kc-i}n\rfloor+1}=\dfrac1n\sum_{c\ge0}\left(\dfrac12\right)^{\lfloor\frac{kc-1}n\rfloor}(n-((kc-1)\bmod n+1)/2)

第二个等号就是考虑到对于一个固定的 c，不同的 \lfloor\frac{kc-i}n\rfloor 只有两种。

\begin{aligned}\mathrm{ans}&=\dfrac1n\sum_{c\ge0}\left(\dfrac12\right)^{\lfloor\frac{kc-1}n\rfloor}(n-((kc-1)\bmod n+1)/2)\\&=\dfrac1{2n}\sum_{c\ge0}\left(\dfrac12\right)^{\lfloor\frac{kc-1}n\rfloor}(2n-(kc-1)\bmod n-1)\\&=\dfrac1{2n}\sum_{c\ge0}\left(\dfrac12\right)^{\lfloor\frac{kc-1}n\rfloor}\left(2n-kc+1+\left\lfloor\dfrac{kc-1}n\right\rfloor n-1\right)\\&=\dfrac1{2n}\sum_{c\ge0}\left(\dfrac12\right)^{\lfloor\frac{kc-1}n\rfloor}\left(2n-kc+\left\lfloor\dfrac{kc-1}n\right\rfloor n\right)\end{aligned}

枚举 r=c\bmod n——

\begin{aligned}\mathrm{ans}&=\dfrac1{2n}\sum_{r=0}^{n-1}\sum_{c\ge0}\left(\dfrac12\right)^{\lfloor\frac{k(cn+r)-1}n\rfloor}\left(2n-k(cn+r)+\left\lfloor\dfrac{k(cn+r)-1}n\right\rfloor n\right)\\&=\dfrac1{2n}\sum_{r=0}^{n-1}\sum_{c\ge0}\left(\dfrac12\right)^{kc+\lfloor\frac{k+r-1}n\rfloor}\left(2n-k(cn+r)+kcn+\left\lfloor\dfrac{kr-1}n\right\rfloor n\right)\\&=\dfrac1{2n}\sum_{r=0}^{n-1}\left(\dfrac12\right)^{\lfloor\frac{kr-1}n\rfloor}\left(2n-kr+\left\lfloor\dfrac{kr-1}n\right\rfloor n\right)\sum_{c\ge0}\left(\dfrac12\right)^{kc}\\&=\dfrac1{2n}\dfrac1{1-(\frac12)^k}\sum_{r=0}^{n-1}\left(\dfrac12\right)^{\lfloor\frac{kr-1}n\rfloor}\left(2n-kr+\left\lfloor\dfrac{kr-1}n\right\rfloor n\right)\end{aligned}

那么问题的困难性就在于求以下三式：

\sum_{r=0}^{n-1}\left(\dfrac12\right)^{\lfloor\frac{kr-1}n\rfloor}\qquad\sum_{r=0}^{n-1}\left(\dfrac12\right)^{\lfloor\frac{kr-1}n\rfloor}r\qquad\sum_{r=0}^{n-1}\left(\dfrac12\right)^{\lfloor\frac{kr-1}n\rfloor}\left\lfloor\frac{kr-1}n\right\rfloor

使用万能 Euclid 算法即可！

时间复杂度 O(T\log n\log V)，如果使用光速幂等技术可以做到 O(T\log n)。

const int P = 1000000007, I = (P + 1) / 2;
struct info
{
    int x, y, ay, ayx, ayy;
    info(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0) : x(a), y(b), ay(c), ayx(d), ayy(e){}
    info operator * (const info& rhs) const {return info((x + rhs.x) % P, (y + rhs.y) % P, (ay + 1ll * qpow(I, y) * rhs.ay) % P, (ayx + 1ll * qpow(I, y) * (rhs.ayx + 1ll * x * rhs.ay % P)) % P, (ayy + 1ll * qpow(I, y) * (rhs.ayy + 1ll * y * rhs.ay % P)) % P);}
};
Euclid<info> e;
int n, k;
int main()
{
    int T; scanf("%d", &T); info U(0, 1, 0, 0, 0), R(1, 0, 1, 1, 0);
    while (T--)
    {
        scanf("%d%d", &n, &k);
        info o = e.solve(k, n, 2 * n - k - 1, n, U, R);
        int A = 8ll * o.ay % P * n % P, B = 4ll * k * (o.ayx - o.ay) % P, C = 4ll * n * (o.ayy - 2ll * o.ay % P) % P;
        int ans = 1ll * ((A - B) % P + C) % P * I % P * qpow(n, P - 2) % P * qpow(1 - qpow(I, k), P - 2) % P;
        printf("%d\n", (ans + P) % P);
    }
    return 0;
}