传送门

题意是说给了n个数字a，m个数字b，k个数字s。

定义了一个集合S，它表示 s 的异或运算封闭群，就是说若干个s异或起来造出来的所有数都在这个集合S里。

定义了一个匹配，取与b数组长度相同的连续一段a数组，当且仅当对应位置异或起来的数字都在S里的时候，称为匹配成功。

问有多少个段能匹配成功。

首先可以用一个线性基来表示这k个s所表示的线性空间。

1. 若a_i 与 b_i均能用这个线性基表示出来，那么异或出来的数一定在群里。

2. 若a_i 与 b_i只有一个不能被线性基表示出来，那么异或出来的数肯定不在群里。

3. 若两个数都不能被线性基表示出来，异或结果是可能在群里的。当且仅当把能用S表示出来的部分删掉后a’=b’。这个其实蛮明显的，比赛的时候没想到。

然后就变成了B串为模式串，A串为原串，做KMP匹配。

温馨提示：本题卡cin，不知道是不是因为HDU编译器版本太旧，关同步也没用。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
int n, m, k;
const int mod = 1e9 + 7;
const int N = 2e5 + 233;
int a[N], b[N], s[N], p[33];
void insert(int x)
{
    for(int i = 30; i >= 0; i--)
    {
        if(!(x >> i)) continue;
        if(!p[i]) 
        {
            p[i] = x;
            break;
        }
        x ^= p[i];
    }
}
void gao(int &x)
{
    for(int i = 30; i >= 0; i--)
    {
        if(!(x >> i & 1)) continue;
        if(p[i]) x ^= p[i];
    }
}
int ne[N], pw[N];
int kmp()
{
    for(int i = 0; i <= m; i++) ne[i] = 0;
    for(int i = 2, j = 0; i <= m; i++)
    {
        while(j && b[i] != b[j + 1]) j = ne[j];
        if(b[i] == b[j + 1]) j++;
        ne[i] = j;
    }
    ll res = 0;
    for(int i = 1, j = 0; i <= n; i++)
    {
        while(j && a[i] != b[j + 1]) j = ne[j];
        if(a[i] == b[j + 1]) j++;
        if(j == m) res = (res + pw[i - m]) % mod , j = ne[j];
    }
    return res % mod;
}
int T; 
int main()
{
    // time_t startt = clock();
    pw[0] = 1;
    for(int i = 1; i <= 200001; i++) pw[i] = pw[i - 1] * 2LL % mod;
    scanf("%d", &T);
    while(T--)
    {
        memset(p, 0, sizeof p);
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
        for(int i = 1; i <= k; i++) scanf("%d", &s[i]), insert(s[i]);
        for(int i = 1; i <= n; i++) gao(a[i]);
        for(int i = 1; i <= m; i++) gao(b[i]);
        printf("%d\n", kmp());
    }
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt) << " ms" << endl;
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt)/CLOCKS_PER_SEC << " s" << endl;
}