八校联测2020-0613 心跳 题解

八校联测2020-0613 心跳 题解

xiaoh 2020-6-18

题意

给定长度为$n$的序列$a$($1\leq n\leq 100,0\leq a_i\leq 10^{18}$),可以进行任意次操作,每次操作将一个数异或上它前面的那个数.求序列严格$LIS$的长度.

题解

首先,由于操作次数没有限制,且操作无明显规律,因而我们考虑找出操作的某些性质以便于处理.我们想到了,是否可以将某个数进行一些次数的操作,从而使它成为前面任意数量的数的异或和再异或上自身.我们先考虑长度为2,3,4的情况.下列式子中字母表示某个任意的数字,而写在一起的字母表示一些数字的异或和.

$n=2:\\ a\;b\\ a\; ab\\$

在上例中,我们成功地把一个数异或到了它后面的一个数上.

$n=3:\\ a\;b\;c\\ a\;ab\;c\\ a\;ab\;abc\\ a\;b\;abc\\ a\;b\;ac\\$

在上例中，我们成功的将一个数异或到了它后面两个数上.注意到,我们其实重复了如下步骤:

1.将$a$异或到b上.

2.将$a,b$异或到$c$上.

3.消除$b$中$a$的影响(即重复$1$的操作)

4.消除$c$中$b$的影响(即重复$2$的操作)

显然,这个过程可以根据序列长度多次递归就能解决.所以,我们可以将$n=4,5,\dots$的情况用类似的方法解决.

所以我们将原问题转化为了可以将任何一个数异或上前面任意多个数,求最大$LIS$的问题.很明显,这样一来这道题就变得可做了.

既然是异或的操作,那么不妨采用线性基和$DP$来进行维护.计$f_{i,j}$为前$i$个数中$LIS$为$j$的最小的$LIS$最后一位的长度.那么我们的线性基就需要支持动态插入,以及动态插入在前$i$个数中以$base$为初值,且终值大于$limit$的最小值,记这个操作为$g(i,base,limit)$.

那么转移方程为

$f_{i,j}=max(f_{i-1,j},g(i-1,a_i,f_{i-1,j-1}))$

边界条件为$f_{i,0}=0$,其余全部为$\infty$.

那么接下来我们考虑如何计算$g$函数.首先我们先将$base$变为能变到的最大值,然后从大到小扫描每一位并检查是否能够满足条件的使原数变小,最后返回即可.时间复杂度$O(n^2\log\;\max a)$.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=110,W=62;
const long long inf=1e18+7;
int n;
class LinearBasis{
private:
	long long f[W+1];
public:
	inline void init()
	{
		memset(f,0,sizeof(f));
	}
	inline void insert(long long x)
	{
		for(int j=W;j>=0;--j)
		{
			if(!(x&(1ll<<j))) continue;
			if(f[j]) x^=f[j];
			else
			{
				for(int i=0;i<j;++i)
				if(x&(1ll<<i)) x^=f[i];
				for(int i=j+1;i<=W;++i)
				if(f[i]&(1ll<<j)) f[i]^=x;
				f[j]=x;
				return; 
			}
		}
	}
	inline long long query(long long x,long long lim)
	{
		for(int i=W;i>=0;--i)
		if(!(x&(1ll<<i))) x^=f[i];
		for(int i=W;i>=0;--i)
		if((x^f[i])>lim) x^=f[i];
		return x>lim? x:inf;
	}
}f;
long long a[MAXN];
long long dp[MAXN][MAXN];
int main()
{
	read(n);
	for(int i=1;i<=n;++i) read(a[i]);
	for(int i=0;i<=n;++i)
	for(int j=1;j<=n;++j) dp[i][j]=inf;
	f.init();
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<=n;++j) dp[i][j]=min(dp[i-1][j],f.query(a[i],dp[i-1][j-1]));
		f.insert(a[i]);
	}
	for(int i=n;i>=1;--i)
	if(dp[n][i]<inf)
	{
		write(i),putchar('\n');
		return 0;
	}
	write(0),putchar('\n');
	return 0;
}