头像

心里没有一点AC数

兰州大学 - 网易浚源工作室 - 西山居 - $\href{https://www.fogsail.net}{Blog}$




离线:3天前



考虑前缀和 $s[i]$,原问题等价于对于一个点 $p$,找到 $s[1\cdots p-1]$ 的一个点 $p’$
使得 $s[p’] \oplus s[p]$ 最大,可以考虑使用可持久化 $\text{trie}$

对于可持久化 $\text{trie}$,$\text{root}(p-1)$ 这个版本中只有区间 $[1\cdots p-1]$ 的信息
利用主席树的思想,可以解决可持久化 $\text{trie}$ 的 $\text{k-query}$ 问题

对于区间 $[1\cdots r]$,要找到一个 $l \in [1\cdots r-1]$,使得 $s_l \oplus s_r$ 为第 $k$ 大
令 $p \leftarrow \text{root}(r-1), \ val \leftarrow s[r]$,从高位到低位检查 $val$ 的第 $b$ 位 $c$
如果 $\textbf{size}(t(p, c \oplus 1)) \geqslant k$,那么 $res += (1 \ll b), \ p \leftarrow t(p, c\oplus 1)$
否则的话,$k’ \leftarrow k - \textbf{size}(t(p, c\oplus 1))$,$p \leftarrow t(p, c)$,递归在 $t(p, c)$ 子树查找第 $k’$ 大

需要注意的是边界,想要让 $r = 1$ 时有意义,必须提前在 $\text{trie}$ 树中插入 $\text{insert}(\text{root}(0), 0)$
表示在 $\text{root}(0)$ 初始化插入一个每个位都是 $0$ 的数

具体来说

  • 对于 $H$ 位的数 $val$,由于要统计 $\text{size}$ 信息,所以递归地插入
    $\textbf{insert}(pre, p, H, val)$,递归的边界是 $H < 0, \text{size}(p) = \text{size}(pre) + 1$
    ($H = 0$ 时插入最后一个字符 $c$,递归执行 $t(p, c)$ 之后,边界 $H = -1$)

  • $res \leftarrow (i, rk(i))$,表示在区间 $[1\cdots i-1]$ 中找到一个 $j$
    使得 $res = s_j \oplus x_i$ 为第 $rk(i)$ 大,很显然一开始 $rk(i) = 1$

  • 建立一个优先队列 $\text{que}$,对于 $\forall \ r \in [1, n]$
    将 $\textbf{ask}(\text{root}(r-1), rk(r), s[r])$ 的结果放入 $\text{que}$ 中

  • 取出堆顶元素,此时堆中最大元素假设为 $(res, p)$
    表示此时 $\exists l \in [1, p)$,使得 $s_l \oplus s_p$ 为第 $1$ 大,其值为 $res$
    将其累加到答案中,删掉 $s_l$,注意要接着找到 $[1, l-1] \cup [l+1, p)$ 中第 $1$ 大,将其放入堆中
    注意到 $[1, l-1] \cup [l+1, p)$ 中的第 $1$ 大,等价于 $[1, p)$ 中的第 $2$ 大
    由此在编程实现上可以更简单一些,一开始令 $rk(i) = 1$,取出堆顶元素 $(res, p)$ 之后
    执行查询 $res’ \leftarrow \textbf{ask}(\text{root}(p), ++rk(p), s[p])$,再继续将 $res’$ 放入堆中

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>
#pragma GCC optimize(2)

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

typedef pair<ll, int> PII;
const int maxn = 500000 + 10, N = maxn * 35;
const int H = 33;
int n, k, rk[maxn], root[maxn];
ll s[maxn];
priority_queue<PII> heap;

// insert(pre, p, H, val)
// ask(root(p), rk, &ans)

class Trie {
public:
    int tot;
    int t[N][2], sz[N];

    Trie() {
        tot = 0;
        memset(t, 0, sizeof t);
        memset(sz, 0, sizeof sz);
    }

    void insert(int pre, int p, int H, ll val) {
        if (H < 0) {
            sz[p] = sz[pre] + 1;
            return;
        }
        int c = val >> H & 1;
        if (pre) t[p][c^1] = t[pre][c^1];
        t[p][c] = ++tot;
        insert(t[pre][c], t[p][c], H-1, val);
        sz[p] = sz[t[p][c]] + sz[t[p][c^1]];
    }

    void ask(int p, int rk, int H, ll val, ll &res) {
        if (H < 0) return;
        int c = val >> H & 1;
        if (sz[ t[p][c^1] ] >= rk) {
            res = (res << 1 | 1);
            ask(t[p][c^1], rk, H-1, val, res);
        }
        else {
            res <<= 1;
            ask(t[p][c], rk - sz[t[p][c^1]], H-1, val, res);
        }
    }
} trie;

void solve() {
    for (int i = 1; i <= n; i++) {
        ll res = 0;
        trie.ask(root[i-1], rk[i], H, s[i], res);
        heap.push({res, i});
    }
    ll ans = 0;
    while (k--) {
        auto x = heap.top(); heap.pop();
        ans += x.first;
        int r = x.second;
        ll res = 0;
        trie.ask(root[r-1], ++rk[r], H, s[r], res);
        heap.push({res, r});
    }
    printf("%lld\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    // init
    memset(root, 0, sizeof root);

    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        ll x;
        scanf("%lld", &x);
        s[i] = s[i-1] ^ x;
        rk[i] = 1;
    }

    // per trie
    root[0] = ++trie.tot;
    trie.insert(0, root[0], H, 0);
    for (int i = 1; i <= n; i++) {
        root[i] = ++trie.tot;
        trie.insert(root[i-1], root[i], H, s[i]);
    }

    // solve
    solve();
}



活动打卡代码 AcWing 256. 最大异或和

trie.001.jpeg

  • 用 $\text{root}[\cdots]$ 数组来定位每个根节点,不妨设 $\text{trie}$ 中字符集合为 $C$,全体字符集为 $A$
    当前插入第 $i$ 个字符串,即执行第 $i$ 个版本,$p \leftarrow \text{root}(i-1)$

  • 新建一个节点 $q$,即 $q = root(i) = ++tot$,假设当前插入字符 $S_j$

  • 如果 $p \neq 0$,对于 $\forall c \in {C}, \ c \neq S_j$,令 $t(q, c) \leftarrow t(p, c)$
    (这一步可以检查 $\forall c \in {A}$ 全体字符集,令 $t(q, c) \leftarrow t(p, c)$,因为下一步 $t(q, S_j)$ 会重新定位到新开的节点上)

  • 新建一个节点,令 $t(q, S_j) = ++tot$,即除了 $S_j$ 指针不同外,$p, q$ 的其余信息完全相同

  • $p \leftarrow t(p, S_j), q \leftarrow t(q, S_j), j \leftarrow j+1$ 直到字符串结尾

  • 可以类似引入一个异或前缀和的概念

$$
\bigoplus_{i = p}^{n} a_p = S_n \oplus S_{p-1}
$$

  • 对于添加操作,很简单 $S_{n+1} = S_n \oplus x, \ n = n+1$

  • 如果令 $p’ = p-1, \ l-1 \leqslant p’ \leqslant r-1$,询问操作实际上就是令 $val = x \oplus S_n$
    求一个位置 $p$,满足 $l-1 \leqslant p \leqslant r-1$,使得 $S_p \oplus val$ 最大
    这个问题如果没有 $p \in [l-1, r-1]$ 的限制,就是最大异或和问题

  • 对于 $p \leqslant r-1$,可以借鉴主席树思想,对 $\text{trie}$ 进行可持久化,在第 $r-1$ 个版本
    即 $\text{root}(r-1)$ 中查询最大异或和路径
    ($p = \text{root}(r-1)$,从高位到低位尽可能沿着和 $val$ 相反的位走)

  • 对于 $p \geqslant l-1$,只要保证异或和路径上所经过点的时间戳 $\geqslant l-1$ 即可
    对于插入操作 $\text{insert}(pre, p, i)$ 表示插入第 $i$ 个字符串
    $k$ 从高位到低位遍历,此时第 $k$ 位的字符为 $c = S_i >> k \& 1$

  • 如果 $pre \neq 0$,令 $t(p, c\oplus 1) \leftarrow t(pre, c\oplus 1)$

  • $t(p, c) = ++tot$,于此同时标记节点时间戳 $dfn(p) = i$,然后和主席树一样同步往下走
    $p \leftarrow t(p, c), \ pre \leftarrow t(pre, c), \textbf{then} \ dfn(p) = i$

const int N = 600000 + 5;
const int maxn = N * 25;
int n, m, s[N], root[N];

class Trie {
public:
    int t[maxn][2], dfn[maxn];
    int tot;

    Trie() {
        tot = 0;
        memset(t, 0, sizeof 0);
        memset(dfn, 0, sizeof 0);
        dfn[0] = -1;
    }

    void insert(int pre, int p, int ver) {
        dfn[p] = ver;
        for (int k = 25; k >= 0; k--) {
            int c = s[ver] >> k & 1;
            if (pre) t[p][c^1] = t[pre][c^1];
            t[p][c] = ++tot;
            p = t[p][c], pre = t[pre][c];
            dfn[p] = ver;
        }
    }

    int ask(int p, int val, int lim) {
        for (int k = 25; k >= 0; k--) {
            int c = val >> k & 1;
            if (dfn[ t[p][c^1] ] >= lim) p = t[p][c^1];
            else p = t[p][c];
        }
        return s[dfn[p]] ^ val;
    }
} trie;

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;

    // init
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        s[i] = s[i-1] ^ x;
        root[i] = ++trie.tot;
        trie.insert(root[i-1], root[i], i);
    }
    while (m--) {
        char cmd[2];
        scanf("%s", cmd);
        if (cmd[0] == 'A') {
            int x;
            scanf("%d", &x);
            root[++n] = ++trie.tot;
            s[n] = s[n-1] ^ x;
            trie.insert(root[n-1], root[n], n);
        }
        else {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            int res = trie.ask(root[r-1], s[n]^x, l-1);
            printf("%d\n", res);
        }
    }
}



trie.001.jpeg

  • 用 $\text{root}[\cdots]$ 数组来定位每个根节点,不妨设 $\text{trie}$ 中字符集合为 $C$,全体字符集为 $A$
    当前插入第 $i$ 个字符串,即执行第 $i$ 个版本,$p \leftarrow \text{root}(i-1)$

  • 新建一个节点 $q$,即 $q = root(i) = ++tot$,假设当前插入字符 $S_j$

  • 如果 $p \neq 0$,对于 $\forall c \in {C}, \ c \neq S_j$,令 $t(q, c) \leftarrow t(p, c)$
    (这一步可以检查 $\forall c \in {A}$ 全体字符集,令 $t(q, c) \leftarrow t(p, c)$,因为下一步 $t(q, S_j)$ 会重新定位到新开的节点上)

  • 新建一个节点,令 $t(q, S_j) = ++tot$,即除了 $S_j$ 指针不同外,$p, q$ 的其余信息完全相同

  • $p \leftarrow t(p, S_j), q \leftarrow t(q, S_j), j \leftarrow j+1$ 直到字符串结尾

  • 可以类似引入一个异或前缀和的概念

$$
\bigoplus_{i = p}^{n} a_p = S_n \oplus S_{p-1}
$$

  • 对于添加操作,很简单 $S_{n+1} = S_n \oplus x, \ n = n+1$

  • 如果令 $p’ = p-1, \ l-1 \leqslant p’ \leqslant r-1$,询问操作实际上就是令 $val = x \oplus S_n$
    求一个位置 $p$,满足 $l-1 \leqslant p \leqslant r-1$,使得 $S_p \oplus val$ 最大
    这个问题如果没有 $p \in [l-1, r-1]$ 的限制,就是最大异或和问题

  • 对于 $p \leqslant r-1$,可以借鉴主席树思想,对 $\text{trie}$ 进行可持久化,在第 $r-1$ 个版本
    即 $\text{root}(r-1)$ 中查询最大异或和路径
    ($p = \text{root}(r-1)$,从高位到低位尽可能沿着和 $val$ 相反的位走)

  • 对于 $p \geqslant l-1$,只要保证异或和路径上所经过点的时间戳 $\geqslant l-1$ 即可
    对于插入操作 $\text{insert}(pre, p, i)$ 表示插入第 $i$ 个字符串
    $k$ 从高位到低位遍历,此时第 $k$ 位的字符为 $c = S_i >> k \& 1$

  • 如果 $pre \neq 0$,令 $t(p, c\oplus 1) \leftarrow t(pre, c\oplus 1)$

  • $t(p, c) = ++tot$,于此同时标记节点时间戳 $dfn(p) = i$,然后和主席树一样同步往下走
    $p \leftarrow t(p, c), \ pre \leftarrow t(pre, c), \textbf{then} \ dfn(p) = i$

const int N = 600000 + 5;
const int maxn = N * 25;
int n, m, s[N], root[N];

class Trie {
public:
    int t[maxn][2], dfn[maxn];
    int tot;

    Trie() {
        tot = 0;
        memset(t, 0, sizeof 0);
        memset(dfn, 0, sizeof 0);
        dfn[0] = -1;
    }

    void insert(int pre, int p, int ver) {
        dfn[p] = ver;
        for (int k = 25; k >= 0; k--) {
            int c = s[ver] >> k & 1;
            if (pre) t[p][c^1] = t[pre][c^1];
            t[p][c] = ++tot;
            p = t[p][c], pre = t[pre][c];
            dfn[p] = ver;
        }
    }

    int ask(int p, int val, int lim) {
        for (int k = 25; k >= 0; k--) {
            int c = val >> k & 1;
            if (dfn[ t[p][c^1] ] >= lim) p = t[p][c^1];
            else p = t[p][c];
        }
        return s[dfn[p]] ^ val;
    }
} trie;

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;

    // init
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        s[i] = s[i-1] ^ x;
        root[i] = ++trie.tot;
        trie.insert(root[i-1], root[i], i);
    }
    while (m--) {
        char cmd[2];
        scanf("%s", cmd);
        if (cmd[0] == 'A') {
            int x;
            scanf("%d", &x);
            root[++n] = ++trie.tot;
            s[n] = s[n-1] ^ x;
            trie.insert(root[n-1], root[n], n);
        }
        else {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            int res = trie.ask(root[r-1], s[n]^x, l-1);
            printf("%d\n", res);
        }
    }
}


活动打卡代码 AcWing 161. 电话列表

将所有字符串插入 trie 中
接着对每个字符串执行查询,遍历 $str[1\cdots n-1]$,如果 trie 中表示某个字符的节点 $p$,$vis(p) \neq 0$
那么就互为前缀

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 1500000 + 10;
const int N = 1e5 + 10;
int n;
char str[N][15];

class Trie {
public:
    int t[maxn][10];
    int vis[maxn];
    int tot;
    Trie() {
        tot = 1;
        memset(t, 0, sizeof t);
        memset(vis, 0, sizeof vis);
    }
    void clear() {
        tot = 1;
        memset(t, 0, sizeof t);
        memset(vis, 0, sizeof vis);
    }

    void insert(const char *str) {
        int p = 1, len = strlen(str);
        for (int i = 0; i < len; i++) {
            int c = str[i]-'0';
            if (!t[p][c]) t[p][c] = ++tot;
            p = t[p][c];
        }
        vis[p]++;
    }

    bool query(const char *str) {
        int p = 1, len = strlen(str);
        for (int i = 0; i < len-1; i++) {
            int c = str[i]-'0';
            p = t[p][c];
            if (vis[p]) return false;
        }
        return true;
    }

} trie;

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    cin >> T;
    while (T--) {
        trie.clear();
        scanf("%d", &n);

        for (int i = 0; i < n; i++) {
            scanf("%s", str[i]);
            trie.insert(str[i]);
        }

        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (trie.query(str[i]) == false) {
                ok = false;
                break;
            }
        }
        ok == true ? puts("YES") : puts("NO");
    }
}



将所有字符串插入 trie 中
接着对每个字符串执行查询,遍历 $str[1\cdots n-1]$,如果 trie 中表示某个字符的节点 $p$,$vis(p) \neq 0$
那么就互为前缀

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 1500000 + 10;
const int N = 1e5 + 10;
int n;
char str[N][15];

class Trie {
public:
    int t[maxn][10];
    int vis[maxn];
    int tot;
    Trie() {
        tot = 1;
        memset(t, 0, sizeof t);
        memset(vis, 0, sizeof vis);
    }
    void clear() {
        tot = 1;
        memset(t, 0, sizeof t);
        memset(vis, 0, sizeof vis);
    }

    void insert(const char *str) {
        int p = 1, len = strlen(str);
        for (int i = 0; i < len; i++) {
            int c = str[i]-'0';
            if (!t[p][c]) t[p][c] = ++tot;
            p = t[p][c];
        }
        vis[p]++;
    }

    bool query(const char *str) {
        int p = 1, len = strlen(str);
        for (int i = 0; i < len-1; i++) {
            int c = str[i]-'0';
            p = t[p][c];
            if (vis[p]) return false;
        }
        return true;
    }

} trie;

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    cin >> T;
    while (T--) {
        trie.clear();
        scanf("%d", &n);

        for (int i = 0; i < n; i++) {
            scanf("%s", str[i]);
            trie.insert(str[i]);
        }

        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (trie.query(str[i]) == false) {
                ok = false;
                break;
            }
        }
        ok == true ? puts("YES") : puts("NO");
    }
}



注意到对于树边 $(x, y)$,$d(y)$ 表示根节点到 $y$ 的距离,那么有
$d(y) = d(x) \oplus e(x, y)$,由于异或操作对于路径重复的部分,值为 $0$
所以 $\oplus (x \to y)$ 实际上就是 $d(x) \oplus d(y)$
只要通过 $\text{dfs}$ 预处理出所有的 $d[x]$,然后转换成最大异或对问题求解即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 3100000 + 5;

class Graph {
public:
    int n;
    int tot = 1;
    vector<int> head, e, ne, ver;

    Graph() = default;
    Graph(int _n) : n(_n) {
        tot = 1;
        head.resize(n), e.resize(n<<1), ne.resize(n<<1), ver.resize(n<<1);
    }

    void add(int a, int b, int c) {
        ver[++tot] = b; e[tot] = c; ne[tot] = head[a]; head[a] = tot;
    }
};

const int N = 100000 + 5;
int n, d[N];
Graph g(N);

class Trie {
public:
    int t[maxn][2];
    int tot;

    Trie() {
        tot = 1;
        memset(t, 0, sizeof t);
    }

    void insert(int x) {
        int p = 1;
        for (int i = 30; i >= 0; i--) {
            int c = x >> i & 1;
            if (!t[p][c]) t[p][c] = ++tot;
            p = t[p][c];
        }
    }

    int query(int x) {
        int res = 0, p = 1;
        for (int i = 30; i >= 0; i--) {
            int c = x >> i & 1;
            if (t[p][!c]) p = t[p][!c], res += (1<<i);
            else p = t[p][c];
        }
        return res;
    }
} trie;

void dfs(int x, int fa) {
    for (int i = g.head[x]; i; i = g.ne[i]) {
        int y = g.ver[i];
        if (y == fa) continue;

        d[y] = d[x] ^ g.e[i];
        dfs(y, x);
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    memset(d, 0, sizeof d);
    scanf("%d", &n);
    for (int i = 0; i < n-1; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a++, b++;
        g.add(a, b, c), g.add(b, a, c);
    }

    // dfs
    dfs(1, 0);

    // trie
    for (int i = 1; i <= n; i++) trie.insert(d[i]);
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, trie.query(d[i]));
    printf("%d\n", res);
}



注意到对于树边 $(x, y)$,$d(y)$ 表示根节点到 $y$ 的距离,那么有
$d(y) = d(x) \oplus e(x, y)$,由于异或操作对于路径重复的部分,值为 $0$
所以 $\oplus (x \to y)$ 实际上就是 $d(x) \oplus d(y)$
只要通过 $\text{dfs}$ 预处理出所有的 $d[x]$,然后转换成最大异或对问题求解即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 3100000 + 5;

class Graph {
public:
    int n;
    int tot = 1;
    vector<int> head, e, ne, ver;

    Graph() = default;
    Graph(int _n) : n(_n) {
        tot = 1;
        head.resize(n), e.resize(n<<1), ne.resize(n<<1), ver.resize(n<<1);
    }

    void add(int a, int b, int c) {
        ver[++tot] = b; e[tot] = c; ne[tot] = head[a]; head[a] = tot;
    }
};

const int N = 100000 + 5;
int n, d[N];
Graph g(N);

class Trie {
public:
    int t[maxn][2];
    int tot;

    Trie() {
        tot = 1;
        memset(t, 0, sizeof t);
    }

    void insert(int x) {
        int p = 1;
        for (int i = 30; i >= 0; i--) {
            int c = x >> i & 1;
            if (!t[p][c]) t[p][c] = ++tot;
            p = t[p][c];
        }
    }

    int query(int x) {
        int res = 0, p = 1;
        for (int i = 30; i >= 0; i--) {
            int c = x >> i & 1;
            if (t[p][!c]) p = t[p][!c], res += (1<<i);
            else p = t[p][c];
        }
        return res;
    }
} trie;

void dfs(int x, int fa) {
    for (int i = g.head[x]; i; i = g.ne[i]) {
        int y = g.ver[i];
        if (y == fa) continue;

        d[y] = d[x] ^ g.e[i];
        dfs(y, x);
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    memset(d, 0, sizeof d);
    scanf("%d", &n);
    for (int i = 0; i < n-1; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a++, b++;
        g.add(a, b, c), g.add(b, a, c);
    }

    // dfs
    dfs(1, 0);

    // trie
    for (int i = 1; i <= n; i++) trie.insert(d[i]);
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, trie.query(d[i]));
    printf("%d\n", res);
}



对每个 $\forall \ A_i$,考虑从高位到低位,$\forall \ i \in [\text{highbit} \to \text{lowbit}]$
要找到这样的一个 $A_j$,满足 $A_j$ 尽可能多的高位与 $A_i$ 不同,这样异或的高位就有尽可能多的 $1$

  • 将所有数按位插入 $\text{trie}$ 中,$p = 1$ 初始化为根节点

  • 遍历每个 $A_i$,$i \in [\text{highbit} \to \text{lowbit}]$ 检查每一位

  • 如果 $\text{trie}(p, !i) \neq 0$,那么顺着 $\text{trie}(p, !i)$ 走
    并且 $res += (1 << i)$

  • 否则沿着 $\text{trie}(p, i)$ 走

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 3100000 + 5;
const int N = 1e5 + 5;
int n, a[N];

class Trie {
public:
    int tot;
    int t[maxn][2];

    Trie() {
        tot = 1;
        memset(t, 0, sizeof t);
    }

    void insert(int x) {
        int p = 1;
        for (int i = 30; i >= 0; i--) {
            int c = (x >> i & 1);
            if (t[p][c] == 0) t[p][c] = ++tot;
            p = t[p][c];
        }
    }
    int query(int x) {
        int res = 0, p = 1;
        for (int i = 30; i >= 0; i--) {
           int c = x >> i & 1;
           if (t[p][!c]) {
               res += (1<<i);
               p = t[p][!c];
           }
           else p = t[p][c];
        }
        return res;
    }
};

Trie trie;

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        trie.insert(a[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, trie.query(a[i]));
    printf("%d\n", res);
}


活动打卡代码 AcWing 143. 最大异或对

对每个 $\forall \ A_i$,考虑从高位到低位,$\forall \ i \in [\text{highbit} \to \text{lowbit}]$
要找到这样的一个 $A_j$,满足 $A_j$ 尽可能多的高位与 $A_i$ 不同,这样异或的高位就有尽可能多的 $1$

  • 将所有数按位插入 $\text{trie}$ 中,$p = 1$ 初始化为根节点

  • 遍历每个 $A_i$,$i \in [\text{highbit} \to \text{lowbit}]$ 检查每一位

  • 如果 $\text{trie}(p, !i) \neq 0$,那么顺着 $\text{trie}(p, !i)$ 走
    并且 $res += (1 << i)$

  • 否则沿着 $\text{trie}(p, i)$ 走

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 3100000 + 5;
const int N = 1e5 + 5;
int n, a[N];

class Trie {
public:
    int tot;
    int t[maxn][2];

    Trie() {
        tot = 1;
        memset(t, 0, sizeof t);
    }

    void insert(int x) {
        int p = 1;
        for (int i = 30; i >= 0; i--) {
            int c = (x >> i & 1);
            if (t[p][c] == 0) t[p][c] = ++tot;
            p = t[p][c];
        }
    }
    int query(int x) {
        int res = 0, p = 1;
        for (int i = 30; i >= 0; i--) {
           int c = x >> i & 1;
           if (t[p][!c]) {
               res += (1<<i);
               p = t[p][!c];
           }
           else p = t[p][c];
        }
        return res;
    }
};

Trie trie;

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        trie.insert(a[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, trie.query(a[i]));
    printf("%d\n", res);
}


活动打卡代码 AcWing 142. 前缀统计

只有在字符串末尾,$\text{cnt}(p) \neq 0$,考虑 $p$ 从根节点 $1$ 开始
沿着模式串 $\text{str}$ 的字符往下走,对路径上的 $\text{cnt}$ 求和, $\sum \text{cnt}(p)$ 就是答案

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 500000 + 10;

class Trie {
public:
    int n;
    int tot;
    vector<vector<int> > t;
    vector<int> cnt;

    Trie() = default;
    Trie(int _n) : n(_n) {
        tot = 1;
        t.resize(n), cnt.resize(n);

        fill(t.begin(), t.end(), vector<int> (26, 0));
        fill(cnt.begin(), cnt.end(), 0);
    }

    void insert(const string &str) {
        int p = 1;
        for (auto x : str) {
            int c = x - 'a';
            if (t[p][c] == 0) t[p][c] = ++tot;
            p = t[p][c];
        }
        cnt[p]++;
    }

    int query(const string &str) {
        int p = 1, res = 0;
        for (auto x : str) {
            int c = x - 'a';
            if (t[p][c] == 0) break;
            p = t[p][c];
            res += cnt[p];
        }
        return res;
    }
};

Trie trie(maxn);

int n, m;

int main() {
    freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    while (n--) {
        string str;
        cin >> str;
        trie.insert(str);
    }
    while (m--) {
        string str;
        cin >> str;
        int res = trie.query(str);
        cout << res << endl;
    }
}