QOJ 8527 Power Divisions 做题记录

给定一个长 $n$ 的序列 $a$，定义一个区间 $[l,r]$ 是好的，当且仅当存在某个 $x$ 使得 $2^x=\sum\limits_{i=l}^r 2^{a_i}$。求将 $a$ 划分为若干个好的区间的方案数，对 $10^9+7$ 取模。

$1\le n\le 3\times 10^5$，$0\le a_i\le 10^6$。

考虑一个好的区间 $[l,r]$ 以及某个 $l\le m<r$ 的 $m$，设 $x=\sum\limits_{i=l}^m 2^{a_i},y=\sum\limits_{i=m+1}^r 2^{a_i}$，观察其需要满足的性质：

• $x$ 和 $y$ 的 lowbit 相同；
• $x$ 和 $y$ 除了 lowbit 外没有位同时为 $1$；
• $x|y$ 的 $1$ 连续（$|$ 为按位或）；

不难发现这是充要的，并且知道 higbit 最高的那个数就可以反推出另一个数。例如若已知 $x=(101100)_2$ 并且它的 higbit 最高，则 $y$ 必须为 $(010100)_2$。下面不妨假定 $x$ 的 higbit 比 $y$ 的高。

那么考虑 cdq 分治，强制钦定某一边的 higbit 是最高的。注意到这样一定能找出所有区间，并且由于每个 $x$ 唯一对应一个 $y$，且某一边的和一定是互不相同的，所以这样也顺带证明了总区间个数是 $O(n\log n)$。

具体的，不妨钦定右侧的 higbit 最高，那么从 $mid$ 往 $l$ 枚举，暴力进位并配合异或哈希求出每一个 $y$；再从 $mid+1$ 往 $r$ 枚举，暴力进位的同时维护 higbit 和 lowbit，这样就可以求出当前需要的 $y$，用哈希表找到这个 $y$ 对应的左端点即可。

另一种情况同理。由于每次最多会让总进位次数 $+1$，所以时间复杂度是正确的。

找到所有区间后直接跑 dp 即可。注意需要开一个 vis 数组来去重。

时间复杂度 $O(n\log n)$，代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#include <ctime>
#include <random>

using namespace std;

template<typename T>
inline void read(T &x)
{
	x=0;
	T w=1;
	char c=getchar();
	while(c<'0'||c>'9') w=(c=='-'?-w:w),c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x*=w;
}

typedef unsigned long long ull;

const int S=300005,MS=2000005;

#define p 1000000007

int n,a[S];
vector<int> lb[S];
mt19937_64 rnd(time(NULL));
ull val[MS],pre[MS];
bool vis[S];
int f[S];

namespace pot
{
	int hb,lb,b[MS];
	ull hs;
	vector<int> tmp;
	inline void init()
	{
		hb=-1,lb=MS;
		hs=0;
		for(int x:tmp) b[x]=0;
		tmp.clear();
	}
	inline void ins(int x)
	{
		b[x]++,hs^=val[x];
		tmp.push_back(x);
		lb=min(lb,x),hb=max(hb,x);
		while(b[x]==2)
		{
			b[x]=0,b[x+1]++,hs^=val[x+1];
			tmp.push_back(x+1);
			if(x==lb) lb++;
			hb=max(hb,x+1);
			x++;
		}
	}
	inline ull que()
	{
		return pre[hb]^pre[lb]^hs;
	}
}

namespace hsh
{
	const int pp=1145143;
	vector<pair<ull,int> > vec[pp];
	vector<int> tmp;
	inline void init()
	{
		for(int x:tmp) vec[x].clear();
		tmp.clear();
	}
	inline void ins(ull x,int y)
	{
		int id=x%pp;
		vec[id].emplace_back(x,y);
		tmp.push_back(id);
	}
	inline int que(ull x)
	{
		int id=x%pp;
		for(auto t:vec[id]) if(t.first==x) return t.second;
		return -1;
	}
}

inline void work(int l,int r)
{
	if(l==r) return lb[r].push_back(l),void();
	int mid=l+r>>1;
	work(l,mid),work(mid+1,r);
	pot::init(),hsh::init();
	for(int i=mid;i>=l;i--)
	{
		pot::ins(a[i]);
		hsh::ins(pot::hs,i);
	}
	pot::init();
	for(int i=mid+1;i<=r;i++)
	{
		pot::ins(a[i]);
		int x=hsh::que(pot::que());
		if(x!=-1) lb[i].push_back(x);
	}
	pot::init(),hsh::init();
	for(int i=mid+1;i<=r;i++)
	{
		pot::ins(a[i]);
		hsh::ins(pot::hs,i);
	}
	pot::init();
	for(int i=mid;i>=l;i--)
	{
		pot::ins(a[i]);
		int x=hsh::que(pot::que());
		if(x!=-1) lb[x].push_back(i);
	}
}

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

int main()
{
	for(int i=0;i<=MS-3;i++) val[i]=rnd();
	for(int i=1;i<=MS-3;i++) pre[i]=pre[i-1]^val[i];
	read(n);
	for(int i=1;i<=n;i++) read(a[i]);
	work(1,n);
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int x:lb[i])
		{
			if(vis[x]) continue;
			vis[x]=true;
			add(f[i],f[x-1]);
		}
		for(int x:lb[i]) vis[x]=false;
	}
	printf("%d\n",f[n]);
	return 0;
}