#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define int long long
const int INF = 1e18;
const int mod = 1e9 + 7;
int rem[300005];
int dp(int n)
{
    if (n < 0)
        return 0;
    if (rem[n])
        return rem[n];
    if (n == 1 || n == 0)
        return 1;
    if (n == 2)
        return 3;
    return rem[n] = (2 * (n - 1) * dp(n - 2) % mod + dp(n - 1) % mod) % mod;
}
void solve()
{
    int n, k;
    cin >> n >> k;
    int ans = n;
    for (int i = 1; i <= k; i++)
    {
        int u, v;
        cin >> u >> v;
        if (u == v)
            ans--;
        else
            ans -= 2;
    }
    cout << dp(ans) << endl;
    return;
}
signed main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

是对其求 ​的结果。

__​

问题归结到了异或最重要的性质： 那么，设满足条件的区间为，则必然有： 如果所求目标的异或和的第位置结果，那么其标记​必然满足一下两个条件之一：

1. ，.
2. ，.

所以，对于查询，所需的就是整体数组异或前缀和 (含 )数组第 位置上为 的总数，然后 的返回0

因为要求必须含有第个数，显然不能.

枚举左右端点的个数，然后乘法原理即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> sum(32);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] ^= a[i - 1];
        for (int j = 31; j >= 0; j--)
        {
            sum[j] += ((a[i] >> j) & 1);
        }
    }
    vector<int> tmp(32);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int tar = a[i] ^ a[i - 1];
        int k = __lg(tar);
        ans += (tmp[k] * (sum[k] - tmp[k]) + (i - tmp[k]) * (n - i + 1 - sum[k] + tmp[k]));
        for (int j = 31; j >= 0; j--)
        {
            tmp[j] += ((a[i] >> j) & 1);
        }
    }
    cout << ans << endl;
    return;
}
int32_t main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define int long long
const int INF = 1e18;
const int mod = 1e9 + 7;
const int maxn = 1e6;
vector<int> ans(maxn + 5);
vector<bool> vis(maxn + 5);
vector<int> prime;
void euler(int n)
{
    vis[1] = true;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            prime.push_back(i);
        }
        for (int j = 0; j < prime.size() && i * prime[j] <= n; j++)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}
void solve()
{
    for (auto p : prime)
    {
        int cnt = p - 1;
        for (int pos = p; pos <= maxn; pos += p)
        {
            int l = pos;
            int r = min(pos + p, maxn);
            (ans[l] += cnt) %= mod;
            if (r == pos + p)
            {
                ans[r] = (ans[r] - cnt + mod) % mod;
            }
            cnt = (p + cnt - 1) % p;
        }
    }
    int calc = 1;
    for (int pos = 4; pos <= maxn; pos += 4, calc++)
    {
        int l = pos;
        int r = min(pos + 4, maxn);
        (ans[l] += (calc & 1) * 2) %= mod;
        if (r == pos + 4)
        {
            ans[r] = (ans[r] - (calc & 1) * 2 + mod) % mod;
        }
    }
    for (int i = 1; i <= maxn; i++)
    {
        (ans[i] += ans[i - 1]) %= mod;
    }
    for (int i = 1; i <= maxn; i++)
    {
        (ans[i] += ans[i - 1]) %= mod;
    }
    return;
}
signed main()
{
    IOS;
    int t;
    cin >> t;
    euler(maxn);
    solve();
    while (t--)
    {
        int n;
        cin >> n;
        cout << ans[n] << endl;
    }
    system("pause");
    return 0;
}