字符串训练之九

吐槽：感觉你只要没做过这种题，基本上是死翘翘的

分析：

性质：考虑将 a从小到大排序以后子序列的最小异或和肯定是产生于相邻两个元素

因此排序之后，我们只要保证选取出来相邻两个数的异或和不小于题目给出的 即可。

考虑将 DP 插入到 Trie 中，每次相当于询问满足ajxorai>=x的f(j)之和，

这个可以直接在 Trie 上 维护子树和，然后从高位到低位计算。

code by std：

#include <bits/stdc++.h>
template <class T>
inline void read(T &x)
{
    static char ch;
    while (!isdigit(ch = getchar()));
    x = ch - '0';
    while (isdigit(ch = getchar()))
        x = x * 10 + ch - '0';
}
const int MaxN = 3e5 + 5;
const int mod = 998244353;
const int MaxLog = 59;
const int MaxNode = MaxN * (MaxLog + 1);
typedef long long s64;
int n, ans;
s64 lower;
s64 a[MaxN];
int nT = 1;
int trans[MaxNode][2], sze[MaxNode];
inline void add(int &x, const int &y)
{
    x += y;
    if (x >= mod)
        x -= mod;
}
inline void modify(s64 x, int val)
{
    int u = 1;

    add(sze[1], val);
    for (int i = MaxLog; i >= 0; --i)
    {
        int c = x >> i & 1;
        if (!trans[u][c])
            trans[u][c] = ++nT;
        u = trans[u][c];
        add(sze[u], val);
    }
}
inline int query(s64 x)
{
    int u = 1, res = 0;
    for (int i = MaxLog; u && i >= 0; --i)
    {
        int c = x >> i & 1, d = lower >> i & 1;
        if (d)
            u = trans[u][c ^ 1];
        else
        {
            add(res, sze[trans[u][c ^ 1]]);
            u = trans[u][c];
        }
    }
    add(res, sze[u]);
    return res;
}
int main()
{
    freopen("xor.in", "r", stdin);
    freopen("xor.out", "w", stdout);
    read(n), read(lower);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    std::sort(a + 1, a + n + 1);
    ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        int cur = (query(a[i]) + 1) % mod;
        add(ans, cur);
        modify(a[i], cur);
    }
    std::cout << ans << std::endl;
    return 0;
}