P13831 【MX-X18-T3】「FAOI-R6」比亚多西-题解

skyx · 2025-05-25 20:45:13 · 题解

P13831 【MX-X18-T3】「FAOI-R6」比亚多西-题解

upd：优化证明，补充知识点。

看了官方解答后才发现自己的做法有多么【数据删除】，给大家分享一下。

简要题意

有一个区间 [1,n] 和一个数 k\in[1,n]。我们在区间上做二分查找：

每次取中点 m=\lfloor (l+r)/2 \rfloor，操作次数 s 加一；
如果 m=k，过程结束；
否则按二分方式更新区间，继续。

最终 s 就是找到 k 所需的二分次数。记这个值为 c_k。
对 n 定义：

f(n)=\sum_{i=1}^n c_i,

即对所有 k\in[1,n] 的查找次数求和。

现在给你多个询问 (L,R)，需要计算：

\sum_{i=L}^R f(i) \pmod{998244353}.

题目分析

我们先考虑函数 f 的求法。手玩容易发现 f 是由一个 1、两个 2、四个 3 等类似的形式组成，这实际上对应了完全二叉树中每层的节点的深度。

我们可以用类似于线段树的方法建树，举个例子：

如果我们对区间 [1,n] 做二分，那么根节点是 m=\lfloor (1+n)/2 \rfloor，它的左右子树分别对应 [1,m-1] 和 [m+1,n]。

举个例子，当 n=7 时的树：

实际上，这样的树被叫做二叉搜索树，对于二叉搜索树，它或者是一棵空树，或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。

显然，这样构造出的树深度是 \lfloor \log_2 n \rfloor + 1（根位于第 1 层）。而每个元素 k 的深度 c_k 就是它在树中的层数，所以 f(n) 就等价于“树上所有结点的深度和”。

我们可以利用下面公式求出 f(n)：

f(n)=h \cdot n-2^{h}+h+1,\quad h=\bigl\lfloor \log_2 n \bigr\rfloor+1

::::info[证明] 对于第 i 层（1\le i\le h-1），该层结点数为 2^{\,i-1}，它们的深度都是 i，因此对总深度的贡献为：

i\cdot 2^{\,i-1}.

最后一层 h 的结点数为：

m=n-\bigl(2^{\,h-1}-1\bigr),

它们的深度都是 h，因此贡献为：

h\cdot m.

把各层贡献相加，就得到总深度和：

{\,f(n)=\sum_{i=1}^{h-1} i\cdot 2^{\,i-1}\;+\;h\Bigl(n-\bigl(2^{\,h-1}-1\bigr)\Bigr)\,}\tag{*}

考虑化简下面这个式子：

S=\sum_{i=1}^{h-1} i\cdot2^{\,i-1}.

我们可以考虑利用恒等式 i=\sum_{j=1}^{i}1，但是这太考验注意力了，怎么办？

你可以发现 T = \sum_{i=1}^{h-1} i \cdot 2^i 是容易计算的：

T = \sum_{i=1}^{h-1} i \cdot 2^i = (h-2) \cdot 2^h + 2.

考虑 S 与 T 的关系：

T = \sum_{i=1}^{h-1} i \cdot 2^i = \sum_{i=1}^{h-1} i \cdot 2 \cdot 2^{i-1} = 2 \sum_{i=1}^{h-1} i \cdot 2^{i-1} = 2S.

因此：

S = \frac{T}{2} = \frac{(h-2) \cdot 2^h + 2}{2} = (h-2) \cdot 2^{h-1} + 1.

代回到 (*)，整理可得 f(n)：

\begin{aligned} f(n) &=\sum_{i=1}^{h-1} i\cdot 2^{\,i-1} \;+\;h\Bigl(n-\bigl(2^{\,h-1}-1\bigr)\Bigr)\\ &=(h-2)2^{\,h-1}+1\;+\;h\cdot n-h\cdot 2^{\,h-1}+h\\ &=h\cdot n+\bigl((h-2)-h\bigr)2^{\,h-1}+h+1\\ &=h \cdot n-2\cdot 2^{\,h-1}+h+1\\ &=\,h\cdot n-2^{\,h}+h+1\,. \end{aligned}

:::: 其实这个东西打完暴力 oeis 可以搜到。

很显然的是 h=\lfloor \log_2 n \rfloor+1 在形如 [2^{h-1},2^h-1] 的区间上不变，从而考虑二进制分组批量求和。

在区间 [l,r] 内，每个 k 的贡献是：

f(k) = i\cdot k - 2^i + i + 1.

那么区间和就是：

\sum_{k=l}^r f(k) = i\cdot \sum_{k=l}^r k \;-\; (r-l+1)\cdot 2^i \;+\; (r-l+1)\cdot(i+1).

其中 \sum_{k=l}^r k 用可以等差数列求和：

\sum_{k=l}^r k = \frac{(l+r)\cdot (r-l+1)}{2}.

代码实现

二进制分组感觉实现细节比较多，需要开 __int128，洛谷可过，梦熊需要卡常。可能需要优雅地取模。

FUN FACT：赛时我在 MXOJ 上提交了近 30 发，最后一个点卡在了 1015ms。

#include <bits/stdc++.h>
using namespace std;
#define int __int128
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void print(int n)
{
    if(n<0)
    {
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n % 10 + '0');
}
const int mod=998244353;
const int inv=499122177;
// 2 在 998244353 下的逆元
int f(int n)
{
    int ans=0;

    for(int i=1; i<=61; i++)   // 枚举 h 的取值范围（因为 n ≤ 2^61），区间 [l, r] 上 h 恒等于 i
    {
        int l=(1ll<<(i-1));    // 区间左端点 l = 2^{i-1}
        if(l>n) break;         // 如果左端点已经超过 n，后面区间都无效
        int r=(1ll<<i)-1;      // 区间右端点 r = 2^i - 1
        if(n<r) r=n;           // 被 n 截断，只取到 n
        int len=(r-l+1)%mod;
        l%=mod;
        r%=mod;
        int sum=(l+r)*len*inv%mod;
        ans=(ans+i*sum-len*(1ll<<i)%mod+len*(i+1)+mod)%mod;
    }
    return ans;

}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=read();

    while(T--)
    {
        int L=read(),R=read();
        print((f(R)-f(L-1)+mod)%mod);
        putchar('\n');
    }

    return 0;
}