HDU 6694 Play Games with Rounddog

发表于 | 阅读数

给你一个字符串$S$，然后$q$个询问，每次给出$S$的一个子串$T$。对于每个询问的子串$T$，Calabash可以在$Ｓ$中选择任意个以T作为后缀的子串，然后生成子串对应数目个石子堆，每堆的石子数量等于$w[对应子串在S中出现的次数]$。然后Rounddog可以从这么多堆石子中选择任意堆的石子（至少选一堆），两人开始玩Nim游戏，Calabash先手。现在问Calabash是否存在必胜策略，如果有输出Calabash在必胜策略下，能够选出来的最多的石子数目。

就是一道裸题，P4301 [CQOI2013] 新Nim游戏,即从大到小取，使得线性基里面元素异或起来为$0$。

建立一个$link$树,第一步倍增的跳到子串所在的集合。那个集合的出现次数，即为所有子树出现。考虑上面的贪心直接，暴力从大到小来插入集合即可。

  • 分析下复杂度，线性基$O(60)$,首先不可能每个点都从结点插到父亲结点。显然一个结点插了$\geq60$次，一定存在$\oplus 0$。所有可以预处理所有结点的答案，询问就是$O(qlogn)$

傻逼题要用$unsigned\ long \ long!$

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;

#define pii pair<ll, int>
#define mk make_pair
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

const int SN = 2e5 + 10;
const int SM = 26;
vector<pii> p;
bool cmp(pii a, pii b)
{
    return a.first > b.first;
}
const int MAXL = 60;
class LinearBase
{
public:
    ll p[MAXL];

    void clear()
    {
        memset(p, 0, sizeof(p));
    }
    bool insert(ll x)
    {

        for (int i = MAXL - 1; i >= 0; i--)
        {
            if (x & (1ll << i))
            {
                if (!p[i])
                {
                    p[i] = x;

                    return true;
                }
                x ^= p[i];
            }
        }
        return false;
    }

} lb[SN];
int fa[SN][23];
ll ans[SN];
ll w[SN];
struct SAM
{
    int trans[SN][SM], link[SN], len[SN], scnt, pre, siz[SN];
    vector<int> g[SN];
    SAM() { scnt = pre = 1; }
    void clear()
    {
        scnt = pre = 1;
        memset(trans, 0, sizeof(trans));
        memset(len, 0, sizeof(len));
        memset(siz, 0, sizeof(siz));
        memset(link, 0, sizeof(link));
        memset(ans, 0, sizeof(ans));
        memset(fa, 0, sizeof(fa));
        p.clear();
    }
    void insert(int id)
    {
        int cur = ++scnt;
        siz[cur] = 1;
        len[cur] = len[pre] + 1;
        int u;

        for (u = pre; u && !trans[u][id]; u = link[u])
            trans[u][id] = cur;
        pre = cur;
        if (!u)
            link[cur] = 1;
        else
        {
            int x = trans[u][id];
            if (len[u] + 1 == len[x])
                link[cur] = x;
            else
            {
                int nc = ++scnt;
                link[nc] = link[x];
                len[nc] = len[u] + 1;
                memcpy(trans[nc], trans[x], sizeof(trans[x]));
                link[cur] = link[x] = nc;
                for (; u && trans[u][id] == x; u = link[u])
                    trans[u][id] = nc;
            }
        }
    }
    void dfs(int x)
    {
        for (int i = 0; i < g[x].size(); i++)
        {
            int to = g[x][i];
            dfs(to);

            siz[x] += siz[to];
        }
    }
    void solve()
    {
        for (int i = 1; i <= scnt; i++)
            g[i].clear();
        for (int i = 2; i <= scnt; i++)
            g[link[i]].push_back(i), fa[i][0] = link[i];
        for (int j = 1; j <= 20; j++)
            for (int i = 2; i <= scnt; i++)
                fa[i][j] = fa[fa[i][j - 1]][j - 1];

        dfs(1);
        //        for(int i=1;i<=scnt;i++)
        //            cout << siz[i]<<" ";
        //        cout <<endl;
        for (int i = 1; i <= scnt; i++)
            lb[i].clear();
        for (int i = 2; i <= scnt; i++)
            p.push_back(mk(w[siz[i]], i));
        sort(p.begin(), p.end(), cmp);
        for (int i = 0; i < p.size(); i++)
        {
            pii now = p[i];
            int u = now.second;
            ll v = now.first;
            while (u != 1 && lb[u].insert(v) == true)
            {
                ans[u] += v;
                u = link[u];
            }
        }
    }
} sam;
int ed[N];
char s[N];
int main()
{
    int T = read();
    while (T--)
    {
        int n = read();
        scanf("%s", s + 1);
        sam.clear();
        for (int i = 1; i <= n; i++)
            scanf("%llu", &w[i]);

        for (int i = 1; i <= n; i++)
            sam.insert(s[i] - 'a'), ed[i] = sam.pre;

        sam.solve();
        int Q = read();
        while (Q--)
        {
            int l = read(), r = read();
            int u = ed[r];
            for (int i = 20; i >= 0; i--)
                if (fa[u][i] != 0 && sam.len[fa[u][i]] >= r - l + 1)
                    u = fa[u][i];

            if (ans[u] == 0)
                printf("-1\n");
            else
                printf("%llu\n", ans[u]);
        }
    }
}