diverta 2019 Programming Contest : E - XOR Partitioning

これはもうちょい手早く解きたかった。
https://atcoder.jp/contests/diverta2019/tasks/diverta2019_e

問題

整数列Aが与えられる。これらをいくつかの境界を挟み複数の部分列に分割した場合、分割した個々の部分列内の値のxorが一致するような分割法は何通りか。

解法

先に数列の累積xorをとっておき、部分列のxorを高速に求められるようにしておこう。

A全体のxorを取った値が0か非0かで分類する。

• 非0の場合、その値をvとする。とすると、分割した個々の値の候補はvしかありえない。
  • よって、直前の分割位置はprefixの累積xorが0かvかどちらかが交互に来るしかないので、単純なDPで解ける。
• 0の場合、分割した個々のxorの選択肢vは多数ある。ここではvを1から全通り総当たりしよう。
  • 上の考え方を応用すると、考えるべきはprefixの累積xorが0かvになる位置だけである。そのような位置は、vを総当たりする過程で1回ずつしか参照しない。一方0となる位置はvが何であっても数え上げで考慮しなければならない。
  • よって、vの登場回数で計算量を抑えられるような方式を考える。
  • 具体的にはprefixの累積xorが0になるような位置だけ座標圧縮し、区間加算・区間和を取れるSegTreeを用いる。
  • 累積xorがvになる位置が来たら、直前の累積xorが0となる位置全部から遷移可能なので、区間和を取ってそのような遷移を数え上げる。
  • 次の遷移先として、それ以降の0全部に遷移可能なので、そのような区間に加算する。

int N;
int A[505050];

ll mo=1000000007;
ll ret;
vector<int> id[1<<20];

template<class V, int ME> class BIT_r {
public:
	V bit[2][1<<ME];
	BIT_r(){clear();};
	void clear() {ZERO(bit);};
	
	void update(int entry, V val0, V val1) {
		entry++;
		while(entry <= 1<<ME) (bit[0][entry-1]+=val0)%=mo, (bit[1][entry-1]+=val1)%=mo, entry += entry & -entry;
	}
	V total(int entry) {
		int e=entry++;
		V v0=0,v1=0;
		while(entry>0) (v0+=bit[0][entry-1])%=mo, (v1+=bit[1][entry-1])%=mo, entry -= entry & -entry;
		return ((e*v0+v1)%mo+mo)%mo;
	}
	void add(int L, int R, V val) { // add val to L<=x<=R
		update(L,val,-val*(L-1)%mo);
		update(R+1,-val,val*R%mo);
	}
};
BIT_r<ll,21> bt;

ll dp[2];
ll V[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int tot=0;
	id[0].push_back(0);
	FOR(i,N) {
		cin>>A[i];
		tot^=A[i];
		id[tot].push_back(i+1);
	}
	
	if(tot==0) {
		ll ret=1;
		FOR(i,id[0].size()-2) ret=ret*2%mo;
		bt.add(0,0,1);
		for(i=1;i<1<<20;i++) if(id[i].size()) {
			FORR(j,id[i]) {
				x=lower_bound(ALL(id[0]),j)-id[0].begin();
				V[j]=bt.total(x-1);
				bt.add(x,1<<20,V[j]);
			}
			ret+=bt.total(1<<20)-bt.total((1<<20)-1);
			FORR(j,id[i]) {
				x=lower_bound(ALL(id[0]),j)-id[0].begin();
				bt.add(x,1<<20,mo-V[j]);
			}
		}
		cout<<(ret%mo+mo)%mo<<endl;
	}
	else {
		dp[0]=1;
		x=0;
		FOR(i,N) {
			x^=A[i];
			if(x==tot) (dp[1]+=dp[0])%=mo;
			if(x==0) (dp[0]+=dp[1])%=mo;
		}
		cout<<dp[0]<<endl;
	}
	
	
}

まとめ

シンプルな問題設定だけど、これ今まで出てなかったのかね。