CF1716E 某种神秘矩阵做法

闲话

我和 @AcaCaca_ duel，然后我写了如下的神奇做法，然后 vector 疯狂 CE，爆了。

为什么没人像我这样做啊喂！看来还是我太菜了

题解

首先众所周知的，序列最大子段和可以用 \(\max +\) 矩阵来做。

考虑一个翻转，其实就是在从下往上递归中某一层所有相邻的两个矩阵进行了交换，换句话说，从左乘右变成了右乘左。

从下往上第 \(i\) 层有 \(2^{i-1}\) 种状态，\(2^{n-i+1}\) 个矩阵，所以时空复杂度都是 \(O(n2^n)\) 的。

屎山代码。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
struct matrix{
	LL a[3][3];
};
matrix operator*(const matrix &x,const matrix &y){
	matrix z;
	memset(z.a,-0x7f,sizeof(z.a));
	for(LL i=0;i<=2;i++){
		for(LL j=0;j<=2;j++)
		  for(LL k=0;k<=2;k++)
		   z.a[i][j]=max(z.a[i][j],x.a[i][k]+y.a[k][j]);
	}
	return z;
}
LL n,i,j,k,m,x;
LL stat=0;
LL b[500005];
const LL inf=0x7fffffffffff;
vector<vector<matrix> > v[19];
vector<matrix> v1;
int main(){
	scanf("%lld",&n);
	for(i=0;i<(1<<n);i++){
		scanf("%lld",&b[i]);
	}
	for(i=0;i<(1<<n);i++){
		matrix tmp;
		tmp.a[0][0]=0,tmp.a[0][1]=b[i],tmp.a[0][2]=b[i],tmp.a[1][0]=-inf,tmp.a[1][1]=b[i],tmp.a[1][2]=b[i],tmp.a[2][0]=-inf,tmp.a[2][1]=-inf,tmp.a[2][2]=0;
		v1.push_back(tmp);
	} 
	v[0].push_back(v1);
	for(i=1;i<=n;i++){
		for(j=0;j<(1<<i);j++){
			v1.clear();
			if((j&(1<<(i-1)))>0){
				for(k=0;k<(1<<(n-i));k++){
					v1.push_back(v[i-1][j^(1<<(i-1))][k*2+1]*v[i-1][j^(1<<(i-1))][k*2]);
				}
				v[i].push_back(v1);
			}
			else{
				for(k=0;k<(1<<(n-i));k++)
				  v1.push_back(v[i-1][j][k*2]*v[i-1][j][k*2+1]);
				v[i].push_back(v1);
			}
		}
	}
	scanf("%lld",&m);
	for(i=1;i<=m;i++){
		scanf("%lld",&x);
		stat^=(1<<x);
		printf("%lld\n",max(0ll,max(v[n][stat][0].a[0][1],v[n][stat][0].a[0][2])));
	}
	return 0;
}