题解：P11465 水上舞者索尼娅

· · 题解

P11465 水上舞者索尼娅

提供一个考场上想出的，不使用快速幂和乘法逆元的倍增做法。

推导

方便起见我们称【一串香蕉（还剩 x 根）】为 x 级牌。

首先观察一下每张 x 级牌使用后会发生什么：

上图中黑色圆圈代表消耗为 1，白色圆圈代表消耗为 0。

观察到我们如果打出一张消耗为 1 的 x 级牌后，继续再把产生的消耗为 0 的牌打光，过程中总计：

我们把“将所有的消耗为 1 的 x 级牌转化为消耗为 1 的 x-1 级牌”称作一轮操作。

如果想要打光手中所有的牌，需要进行 n 轮这样的操作。第 i 轮操作中，初始手中会有 (k+1)^{i-1} 张牌，每张牌都会产生 k+1 次出牌，也就是说第 i 轮操作最终产生总计 (k+1)^i 次出牌。

那么显然的，答案就是：\sum \limits_{i=1}^{n} (k+1)^i。

实现

方便起见我们令 m=k+1，我们可以把求和的每一项都写成 m 的 2 的幂数次幂相乘的形式，我们以前 8 项为例：

将每项像这样分解开之后，我们可以发现第 5 到 8 项可以再作整理：

\begin{aligned} m^1m^4+m^2m^4+m^1m^2m^4+m^8 &= (m^1+m^2+m^1m^2+m^4)m^4\\ &= m^4\cdot\sum \limits_{i=1}^{4} m^i \end{aligned}

这启发了我们，当 n=2^p 时有：

\begin{aligned} \sum \limits_{i=1}^{2^p} m^i &= \sum \limits_{i=1}^{2^{p-1}} m^i + m^{2^{p-1}+1} + m^{2^{p-1}+2} + \cdots + m^{2^p}\\ &= \sum \limits_{i=1}^{2^{p-1}} m^i + m^{2^{p-1}}(m^1 + m^2 + \cdots + m^{2^{p-1}})\\ &= \sum \limits_{i=1}^{2^{p-1}} m^i + m^{2^{p-1}} \cdot \sum \limits_{i=1}^{2^{p-1}} m^i\end{aligned}

于是我们可以使用倍增的思路来求出所有 n 可以表示为 2^p 时的结果。

当 n=2^p 时，我们可以通过 \sum \limits_{i=1}^{2^{p+1}} m^i = \sum \limits_{i=1}^{2^p} m^i + m^{2^p} \cdot \sum \limits_{i=1}^{2^p} m^i 来将 n 倍增至 2^{p+1}。

如果 n 不能表示为上述形式，则需要继续递归求解。

我们假设遇到了 2^p < n < 2^{p+1} 的情况，可以列出式子：

\begin{aligned} \sum \limits_{i=1}^{n} m^i &= \sum \limits_{i=1}^{2^p} m^i + m^{2^p+1} + m^{2^p+2} + \cdots + m^n\\ &= \sum \limits_{i=1}^{2^p} m^i + m^{2^p}(m^1 + m^2 + \cdots + m^{n-2^p})\\ &= \sum \limits_{i=1}^{2^p} m^i + m^{2^p} \cdot \sum \limits_{i=1}^{n-2^p} m^i \end{aligned}

所以我们可以继续递归求出 \sum \limits_{i=1}^{n-2^p} m^i，再将其乘上 m^{2^p} 加入答案即可。

像这样每次递归消掉一个最大的 2^p，最终即可得到答案。

时间复杂度为 \mathcal{O}(T (\log n)^2)。

代码

#include<bits/stdc++.h> 
using namespace std;
#define ll long long
const int mo=1e9+7;
ll t,n,k;
int calc(ll m,ll n){
    ll re=m,tot=1;   // re 为返回值，tot 标记求和到第几项。 
    ll mt=m;         // mt 为目前为止最大的 m 的 2 的幂数次幂。 
    while(tot*2<=n){
        re=(re+re*mt)%mo;
        tot*=2;
        mt=(mt*mt)%mo;
    }
    if(tot==n)return re;
    int rre=calc(m,n-tot);
    return (re+rre*mt)%mo;
}
void solve(){
    cin>>n>>k;
    ll m=k+1;
    ll ans=calc(m,n);
    cout<<ans<<endl;
    return;
}
int main(){
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

后日谈

这个做法在比赛当晚的讲评环节收获了出题人的不点名表扬，感到非常荣幸。实际上真的是因为我忘打印快速幂板子还不会乘法逆元才憋出来的。