专栏文章

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

sskyx
P13831题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip7d2v4
此快照首次捕获于
2025/12/03 07:21
3 个月前
此快照最后确认于
2025/12/03 07:21
3 个月前
查看原文

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

upd：优化证明，补充知识点。
看了官方解答后才发现自己的做法有多么【数据删除】，给大家分享一下。

简要题意

有一个区间 [1,n][1,n] 和一个数 k∈[1,n]k\in[1,n]。我们在区间上做二分查找：
  • 每次取中点 m=⌊(l+r)/2⌋m=\lfloor (l+r)/2 \rfloor，操作次数 ss 加一；
  • 如果 m=km=k，过程结束；
  • 否则按二分方式更新区间，继续。
最终 ss 就是找到 kk 所需的二分次数。记这个值为 ckc_k。
对 nn 定义：
f(n)=∑i=1nci,f(n)=\sum_{i=1}^n c_i,
即对所有 k∈[1,n]k\in[1,n] 的查找次数求和。
现在给你多个询问 (L,R)(L,R)，需要计算：
∑i=LRf(i)(mod998244353).\sum_{i=L}^R f(i) \pmod{998244353}.

题目分析

我们先考虑函数 ff 的求法。手玩容易发现 ff 是由一个 11、两个 22、四个 33 等类似的形式组成，这实际上对应了完全二叉树中每层的节点的深度。
我们可以用类似于线段树的方法建树，举个例子：
如果我们对区间 [1,n][1,n] 做二分，那么根节点是 m=⌊(1+n)/2⌋m=\lfloor (1+n)/2 \rfloor，它的左右子树分别对应 [1,m−1][1,m-1] 和 [m+1,n][m+1,n]。
举个例子，当 n=7n=7 时的树：
  • 实际上，这样的树被叫做二叉搜索树，对于二叉搜索树，它或者是一棵空树，或者是具有下列性质的二叉树：
    • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    • 它的左、右子树也分别为二叉排序树。
显然，这样构造出的树深度是 ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1（根位于第 11 层）。而每个元素 kk 的深度 ckc_k 就是它在树中的层数，所以 f(n)f(n) 就等价于“树上所有结点的深度和”。
我们可以利用下面公式求出 f(n)f(n)： f(n)=h⋅n−2h+h+1,h=⌊log⁡2n⌋+1f(n)=h \cdot n-2^{h}+h+1,\quad h=\bigl\lfloor \log_2 n \bigr\rfloor+1
证明
对于第 ii 层（1≤i≤h−11\le i\le h-1），该层结点数为 2 i−12^{\,i-1}，它们的深度都是 ii，因此对总深度的贡献为：
i⋅2 i−1. i\cdot 2^{\,i-1}.
最后一层 hh 的结点数为：
m=n−(2 h−1−1),m=n-\bigl(2^{\,h-1}-1\bigr),
它们的深度都是 hh，因此贡献为：
h⋅m.h\cdot m.
把各层贡献相加，就得到总深度和：
 f(n)=∑i=1h−1i⋅2 i−1  +  h(n−(2 h−1−1)) (*){\,f(n)=\sum_{i=1}^{h-1} i\cdot 2^{\,i-1}\;+\;h\Bigl(n-\bigl(2^{\,h-1}-1\bigr)\Bigr)\,}\tag{*}
考虑化简下面这个式子：
S=∑i=1h−1i⋅2 i−1.S=\sum_{i=1}^{h-1} i\cdot2^{\,i-1}.
我们可以考虑利用恒等式 i=∑j=1i1i=\sum_{j=1}^{i}1，但是这太考验注意力了，怎么办？
你可以发现 T=∑i=1h−1i⋅2iT = \sum_{i=1}^{h-1} i \cdot 2^i 是容易计算的：
T=∑i=1h−1i⋅2i=(h−2)⋅2h+2.T = \sum_{i=1}^{h-1} i \cdot 2^i = (h-2) \cdot 2^h + 2.
考虑 SS 与 TT 的关系：
T=∑i=1h−1i⋅2i=∑i=1h−1i⋅2⋅2i−1=2∑i=1h−1i⋅2i−1=2S.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=T2=(h−2)⋅2h+22=(h−2)⋅2h−1+1.S = \frac{T}{2} = \frac{(h-2) \cdot 2^h + 2}{2} = (h-2) \cdot 2^{h-1} + 1.
代回到 (∗)(*)，整理可得 f(n)f(n)：
f(n)=∑i=1h−1i⋅2 i−1  +  h(n−(2 h−1−1))=(h−2)2 h−1+1  +  h⋅n−h⋅2 h−1+h=h⋅n+((h−2)−h)2 h−1+h+1=h⋅n−2⋅2 h−1+h+1= h⋅n−2 h+h+1 .\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=⌊log⁡2n⌋+1h=\lfloor \log_2 n \rfloor+1 在形如 [2h−1,2h−1][2^{h-1},2^h-1] 的区间上不变，从而考虑二进制分组批量求和。
在区间 [l,r][l,r] 内，每个 kk 的贡献是：
f(k)=i⋅k−2i+i+1.f(k) = i\cdot k - 2^i + i + 1.
那么区间和就是：
∑k=lrf(k)=i⋅∑k=lrk  −  (r−l+1)⋅2i  +  (r−l+1)⋅(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).
其中 ∑k=lrk\sum_{k=l}^r k 用可以等差数列求和：
∑k=lrk=(l+r)⋅(r−l+1)2.\sum_{k=l}^r k = \frac{(l+r)\cdot (r-l+1)}{2}.

代码实现

二进制分组感觉实现细节比较多，需要开 __int128，洛谷可过，梦熊需要卡常。可能需要优雅地取模。
FUN FACT：赛时我在 MXOJ 上提交了近 3030 发，最后一个点卡在了 1015ms。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...