自动搬运

查看原文

来自洛谷，原作者为

	xh39 **

搬运于2025-08-24 22:27:00，当前版本为作者最后更新于2021-01-03 23:26:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

注:正解为暴力的优化,请先看暴力。

本篇题解中的时间复杂度均为一组数据中的时间复杂度,所以最终复杂度还要乘数据组数$t$。

?

小 L 想请你帮他计算出$cover(A,B)$的期望值与$\frac{n(n+1)}{2}$ 的乘积对$1, 000, 000, 007$ 取模的结果，可以发现此结果一定是一个整数。

为什么是整数?遇到乘...一定是整数先思考为什么,大部分时候都有利于做题。

任意选两种情况总共有$C_{n}^{2}=\frac{n(n+1)}{2}$种方案,所以题目就是要求$sum\{cover(i,j)\}(0<i<=j<=n)$,即所有cover的和。

暴力O(n)

貌似直接算答案时间复杂度为$O(n^2\times log_2(n))$,所以肯定不行。

于是想到了算贡献.可是怎么算贡献呢?

设f[n]为长度为n的线段树的贡献。left为左子树,right右子树。

我们可以来模拟一下转移的过程,转移的过程是一种类似点分治而非点分治的过程。

        1,7
       /   \
     1,4    5,7
    / \     /  \
 1,2 3,4  5,6  7
 /\  /\   /\
1 2 3 4  5 6
(节点数为7的线段树)

首先,按照点分治的思路,先算子树内的贡献:$f[left]+f[right]$

然后算跨两子树间的贡献:$[1,7]$这个区间需从$[1,4]$选出一部分,$[5,7]$选出一部分,由于两个部分互不干扰,所以可以相加。

$[1,4]$的贡献将被裂开为两个区间$[1,4]和[5,r](r>=5)$,因为此贡献要跨两子树,所以r一定位于右子树。又因为$r$一定要在这棵树内,所以$r<=7$,所以$r$一共有$7-5+1=3(种)$取值。而不管r取哪一个,对左区间$[1,4]$不会构成影响,所以左子树的贡献为$3$。

同理,右子树贡献为$4$。那么我们可以得出结论:左子树将会被贡献$size[right]$次,右子树将会被贡献$size[left]$次。

那是不是$f[left]\times size[right]+f[right] \times size[left]$就是跨两子树的贡献了呢?

看起来似乎很正确,但模拟几组小数据会发现实际上大了。

我们多算了哪些呢?原来是在裂开$[1,7]$时,裂开成了$[1,4]和[5,7]$,而$cover(1,4)$包括了$[1,2]$的贡献。而我们在计算时就变成了$[1,2]和[5,7]$,显然区间不连续。

那怎么办呢?怎么避免不连续的区间?直接加工f肯定不行(至少我想了几种方向都不行),那我们就多设状态。

观察$[1,4]与[5,7]$如何才能构成一个连续的区间?先讨论左子树$[1,4]$的贡献。肯定区间$[1.4]$取出来的一段子区间必须右端点是$4$。换个说法:这个子区间必须是$[1,4]$的后缀,$[1,4],[2,4],[3,4]或[4,4]$。而右子树$[5,7]$的贡献一定是$[5,5],[5,6]或[5,7]$。

所以需增加2个状态:$fl[n]$表示长度为$n$的线段树的后缀区间的$cover和$(即$sum\{cover(i,n)\}(0<i<=n)$)。$fr[n]$表示后缀区间cover和。

至于这两个状态如何转移,应该很容易,这里就不再解释了。看下面的式子应该能看懂。不懂就画一棵线段树手动推一下。

$fl[n]=fl[left]+(fl[right]+right)-1$

注:+left的原因是每个右子树的前缀区间都需要左儿子来覆盖,即加left个1。

-1的原因是覆盖整个区间时会用左儿子和右儿子2个结点覆盖,事实上直接选用根节点就可以了。

同理,就不列$fr$了,具体见代码。

得出$f[n]=(f[left]+f[right])+(fr[left]\times size[right]+fl[right]\times size[left])$//注:这里加分间打括号的原因是区分子树内和跨两子树。

关于如何求left和right,就看你的线段树基础了。$size[left]=(size[root])/2向上取整,size[right]=size[root]/2向下取整$,至于怎么证,我也不知道。

暴力代码(由于反正会tle,就没开long long和取模了):

#include<iostream>
using namespace std;
int fl(int n){
	if(n==1){ //边界条件。当只有1个结点时3个状态都为1。
		return 1;
	}
	int left,right=n>>1;
	left=n-right; //向上取整=n-向下取整。
	return fl(left)+fl(right)+right-1;
}
int fr(int n){
	if(n==1){
		return 1;
	}
	int left,right=n>>1;
	left=n-right;
	return fr(left)+left+fr(right)-1;
}
int fm(int n){
	if(n==1){
		return 1;
	}
	int left,right=n>>1;
	left=n-right;
	return fm(left)+fm(right)+fr(left)*(right)+fl(right)*(left)-1;
}
int main(){
	int t,n,i;
	cin>>t;
	for(i=0;i<t;i++){
		scanf("%d",&n);
		cout<<fm(n)<<"	"<<fl(n)<<"	"<<fr(n)<<endl;
	}
}

正解$O(log_{2}(n))$

发现递归查询了很多相同的状态,很容易想到记忆化。但是有$n<=10^{18}$,那么多状态数组存不下。这里有3种办法。

1.哈希。(状态较多时容易被卡,不推荐,除非是在没别的办法)

2.map。(时间复杂度变为$O(log_2(n)^{2}$),可能tle。(注意本题多组数据,需要乘$t=1000$,而map常数较大,递归常数也大,不冒这个风险,除非实在没别的办法)

3.本题解的方法,后面介绍。

观察我们需要用到哪些状态。

为方便,$(n+a)/b$表示为$n+a/b$,即先算加法。上节点为左子树。

$n<^{n+1/2<^{n+3/4}_{n+1/4}}_{n+0/2<^{n+2/4^{............}}_{n+0/4}}$

再画多一点节点(由于latex的一些性质,这里只画了3层),就会发现,第$i$层的节点只会是$n+a/(2^{i})(a为0至2^i的全排列)$

为什么a为全排列呢?可以用二进制解释。

一个第$i$层节点数为$n+a/b$的结点,左结点一定是$n+(a+2^i)/b$。右节点也为$n+a/b$。那么左节点即为二进制第$i$位为$1$。否则为$0$。

那么左右子树的二进制序列就变成了全排列。

那知道了$a$为$n+a/(2^i)$全排列。那么就可以得出一个性质:第$i$层子树大小要么为$(n/2^i)$,要么为$(n/2^i+1)$。

然后就得出了一个性质:同一层只有$2$种节点,且相差为$1$,这让我们想到了奇偶性讨论。那我们可以这样设状态。

$f[step][odd]$表示在第$step$层的节点为(奇/偶)的子树的f值。

然后这道题就解决了。代码不长,看起来有60行左右的原因是很多都是复制的。所以实际只有几个递推式是核心内容。

#include<iostream>
#include<cstring>
using namespace std;
long long l[60][2],r[60][2],m[60][2];
#define mod 1000000007
long long fl(long long n,int step){
	if(l[step][n&1ll]){
		return l[step][n&1ll];
	}
	if(n==1ll){
		return 1ll;
	}
	long long left,right=n>>1ll;
	left=n-right;
	l[step][n&1ll]=(fl(left,step+1)+fl(right,step+1ll)+right-1ll)%mod;
	return l[step][n&1ll];
}
long long fr(long long n,int step){
	if(r[step][n&1ll]){
		return r[step][n&1ll];
	}
	if(n==1ll){
		return 1ll;
	}
	long long left,right=n>>1ll;
	left=n-right;
	r[step][n&1ll]=(fr(left,step+1)+left+fr(right,step+1)-1ll)%mod; 
	return r[step][n&1ll];
}
long long fm(long long n,int step){
	if(m[step][n&1ll]){
		return m[step][n&1ll];
	}
	if(n==1ll){
		return 1ll;
	}
	long long left,right=n>>1ll;
	left=n-right;
	m[step][n&1ll]=(fm(left,step+1)+fm(right,step+1)+fr(left,step+1)*(right%mod)+fl(right,step+1)*(left%mod)-1ll)%mod;//left,right在做乘法时一定要先模mod,因为它们可能很大。
	return m[step][n&1ll];
}
int main(){
	long long t,i,n,t1,t2,t3;
	cin>>t;
	for(i=0;i<t;i++){
		memset(l,0,sizeof(l)); //与普通记忆化不同的是,一定要清空,因为对于不同的n,f[step][odd]的含义不一样了。
		memset(r,0,sizeof(r));
		memset(m,0,sizeof(m));
		scanf("%lld",&n);
		cout<<fm(n,0)<<endl;
	}
}

一些题外话

官方题解讲得有那么一定的清楚,本人只看懂了"算贡献"3个字。于是照着这3个字思考了一周。所以题解中有我的思考过程,可能会很啰嗦。

$\color{green}\text{Happy new year!}$