yukicoder : No.1142 XOR と XOR

E問題でハマってしまった。
https://yukicoder.me/problems/no/1142

問題

2つの整数列A,Bが与えられる。
A,Bから空でない連続した部分列を1つずつ取り出したとき、全体のxorを取った値がKとなるのは何通りか。

解法

f(x) := Aの連続した部分列のうち、xorがxとなるものの組み合わせ
g(x) := Bの連続した部分列のうち、xorがxとなるものの組み合わせ

とするとf(i)*g(K^i)の総和を取ればよい。
A,Bの取りえる値をn通りとすると、f,gはDPでO(n(|A|+|B|))で間に合う。

int N,M,K;
int A[202020],B[202020];
ll from[1024],to[1024];
ll S[1024],T[1024];
const ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) {
		cin>>x;
		ZERO(to);
		from[0]++;
		FOR(j,1024) S[j^x]+=to[j^x]=from[j];
		swap(from,to);
	}
	ZERO(from);
	FOR(i,M) {
		cin>>x;
		ZERO(to);
		from[0]++;
		FOR(j,1024) T[j^x]+=to[j^x]=from[j];
		swap(from,to);
	}
	
	ll ret=0;
	FOR(i,1024) S[i]%=mo, T[i]%=mo;
	FOR(i,1024) (ret+=S[i]*T[i^K])%=mo;
	cout<<ret<<endl;
}

まとめ

最初O(n(|A|+|B|))は想定解じゃないだろうなと思ったのだけど、よく見たらnがさほど大きくないのでどうになかった。