yukicoder : No.1493 隣接xor

こちらも典型寄り。
https://yukicoder.me/problems/no/1493

問題

整数列Aが与えられる。
隣接する2要素を選び、そのxorに置き換えるという作業を、要素が2個以上ある限り任意に行えるとする。
この時、最終的に得られる数列は何通りか。

解法

Aの累積xorを取った数列Sを考える。
あとはこのSの部分列のうち異なるものを数え上げればよい。
dp[i] := Sのprefix i個のうち異なる部分列の数
とすると、

• dp[0]=1
• dp[i]=sum(dp[0....(i-1)]]) ただし、S[i]=S[j]となるi未満最大のjがあれば、dp[j]だけ引く

で順に計算できる。

int N;
int A[202020];
int S[202020];

ll sum;
map<int,ll> V;
ll dp[202020];
const ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]^A[i];
	}
	dp[N]=1;
	V[-1]=1;
	sum=1;
	for(i=N-1;i>=0;i--) {
		dp[i]=sum;
		if(V.count(S[i])) {
			(sum+=mo-V[S[i]])%=mo;
		}
		V[S[i]]=dp[i];
		(sum+=dp[i])%=mo;
	}
	cout<<dp[0]<<endl;
}

まとめ

なんか最近yukicoderの問題が多くてなかなかいろいろ追い付かない。