TJOI2019

TJOI2019

甲苯先生的字符串

按照题意将转移矩阵建出来,然后直接矩阵快速幂.(注意\(ab\)\(ba\)不算同一种情况).

复杂度\(O(26^3 \log n)\)

代码:

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
/*
* 5508.cpp
* This file is part of 5508
*
* Copyright (C) 2019 - ViXbob
*
* 5508 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 5508 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 5508. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 1e9 + 7;

ll n;
bool G[50][50];
char s[maxn];

inline ll read() {
char ch = getchar(); ll u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

struct Matrix {
int H, W;
vector<vector<int> > mat;
Matrix(int a = 0, int b = 0) {
H = a; W = b;
mat.resize(H);
rep(i, 0, H - 1) mat[i].resize(W);
}

vector<int> &operator [] (const int x) { return mat[x]; }

Matrix operator * (const Matrix &t) const {
Matrix rnt(H, t.W);
rep(i, 0, H - 1) rep(j, 0, t.W - 1) rep(k, 0, W - 1)
rnt[i][j] = pls(rnt[i][j], 1ll * mat[i][k] * t.mat[k][j] % P);
return rnt;
}

Matrix operator ^ (ll k) const {
Matrix rnt = (*this), x = (*this);
for(ll i = k - 1; i; i >>= 1, x = x * x) if(i & 1) rnt = rnt * x;
return rnt;
}
} A, Trans;

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); scanf("%s", s + 1);
int Len = strlen(s + 1), ans = 0;
A = Matrix(1, 26);
Trans = Matrix(26, 26);
rep(i, 0, 25) A[0][i] = 1;
rep(i, 1, Len - 1) Trans[s[i] - 'a'][s[i + 1] - 'a'] = 1;
for(auto &u : Trans.mat) for(auto &v : u) v ^= 1;
Trans = Trans ^ (n - 1);
A = A * Trans;
for(auto &v : A.mat[0]) ans = pls(ans, v);
cout << ans << endl;
return 0;
}

甲苯先生的滚榜

对于做得题目个数相同的人都丢到同一颗\(\text{Splay}\)里,用平衡树维护罚时排名,然后在搞一个树状数组维护一下前缀和就做完了.

代码:

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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
/*
* 5509.cpp
* This file is part of 5509
*
* Copyright (C) 2019 - ViXbob
*
* 5509 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 5509 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 5509. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

int T, C[maxn], Sum, mx, R[maxn], Tim[maxn], m, n;

typedef unsigned int ui ;
ui randNum( ui& seed , ui last , const ui m){
seed = seed * 17 + last ; return seed % m + 1;
}

ui seed, last;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

inline void modify(int p, int x) { for(int i = p; i < maxn; i += (-i & i)) C[i] += x; }
inline int query(int p, int rnt = 0) { for(int i = p; i; i -= (-i & i)) rnt += C[i]; return rnt; }

namespace Splay {
int tot, root[maxn];
#define who(x) (t[t[x].fa].ch[1] == x)
#define Ls(x) t[x].ch[0]
#define Rs(x) t[x].ch[1]
struct Node {
int num, size, ch[2], fa, w;
inline void clear() { num = size = ch[0] = ch[1] = fa = w = 0; }
} t[maxn * 20];

inline void clear() {
rep(i, 1, tot) t[i].clear();
tot = 0;
memset(root, 0, sizeof(root));
}

inline void pushup(int x) {
t[x].size = t[Ls(x)].size + t[x].num + t[Rs(x)].size;
}

inline void rotate(int x) {
int y = t[x].fa, z = t[y].fa, w = !who(x);
t[z].ch[who(y)] = x; t[x].fa = z;
t[y].ch[w ^ 1] = t[x].ch[w]; t[t[x].ch[w]].fa = y;
t[x].ch[w] = y; t[y].fa = x;
pushup(y); pushup(x);
}

inline void splay(int x, int goal, int &root) {
while(t[x].fa != goal) {
int y = t[x].fa, z = t[y].fa;
if(z != goal) rotate(who(x) ^ who(y) ? x : y);
rotate(x);
}
root = goal ? root : x;
}

inline int findx(int x, int root) {
int o = root;
while(o) {
if(t[o].w == x) return o;
if(!t[o].ch[t[o].w < x]) break;
o = t[o].ch[t[o].w < x];
} return o;
}

inline void insert(int w, int Num) {
int Rt = root[Num];
if(Rt == 0) {
root[Num] = ++tot;
t[tot].num = 1;
t[tot].w = w;
pushup(tot);
return;
}
int z = findx(w, Rt);
if(t[z].w == w) {
splay(z, 0, root[Num]);
t[z].num++; pushup(z);
} else {
t[z].ch[t[z].w < w] = ++tot;
t[tot].w = w; t[tot].fa = z;
splay(tot, 0, root[Num]);
t[tot].num = 1; pushup(tot);
}
}

inline int Pre(int w, int root) {
int o = root, rnt = 0, Mx = 0;
while(o) {
if(t[o].w < w) {
if(t[o].w > Mx) Mx = t[o].w, rnt = o;
o = t[o].ch[1];
} else o = t[o].ch[0];
} return rnt;
}

inline int Suc(int w, int root) {
int o = root, rnt = 0, Mn = inf;
while(o) {
if(t[o].w > w) {
if(t[o].w < Mn) Mn = t[o].w, rnt = o;
o = t[o].ch[0];
} else o = t[o].ch[1];
} return rnt;
}

inline void del(int w, int Num) {
int Rt = root[Num], x = findx(w, Rt);
int pre = Pre(w, Rt), suc = Suc(w, Rt);
if(!pre || !suc) splay(x, 0, root[Num]);
if(pre == 0 && suc == 0) {
if(t[x].num == 1) t[x].clear(), root[Num] = 0;
else t[x].num--, pushup(x);
return;
}
if(pre == 0) {
if(t[x].num == 1) {
root[Num] = Rs(x);
t[Rs(x)].fa = 0;
t[x].clear();
} else t[x].num--, pushup(x);
} else if(suc == 0) {
if(t[x].num == 1) {
root[Num] = Ls(x);
t[Ls(x)].fa = 0;
t[x].clear();
} else t[x].num--, pushup(x);
} else {
splay(pre, 0, root[Num]); splay(suc, pre, root[Num]);
if(t[x].num == 1) {
Ls(suc) = 0;
pushup(suc);
t[x].clear();
} else t[x].num--, pushup(x), pushup(suc), pushup(pre);
}
}

inline int Rnk(int w, int Num) {
int o = root[Num], rnt = 0;
while(o) {
if(t[o].w < w) {
rnt += t[Ls(o)].size;
rnt += t[o].num;
o = Rs(o);
} else if(t[o].w == w) {
rnt += t[Ls(o)].size;
break;
} else o = Ls(o);
} return rnt;
}
} using namespace Splay;

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
T = read(); last = 7;
while(T--) {
m = read(); n = read(); seed = read();
memset(C, 0, sizeof(C));
memset(R, 0, sizeof(int) * (m + 5));
memset(Tim, 0, sizeof(int) * (m + 5));
clear();
while(n--) {
int Ria = randNum(seed, last, m);
int Rib = randNum(seed, last, m);
// cerr << Ria << " " << Rib << endl;
if(R[Ria] != 0) {
del(Tim[Ria], R[Ria]);
modify(R[Ria], -1);
}
Tim[Ria] += Rib; R[Ria]++;
// cerr << Tim[Ria] << " " << R[Ria] << endl;
// cerr << Rnk(Tim[Ria], root[R[Ria]]) << " " << query(maxn - 1) << " " << query(R[Ria]) << endl;
last = Rnk(Tim[Ria], R[Ria]) + query(maxn - 1) - query(R[Ria]);
printf("%d\n", last);
modify(R[Ria], 1);
insert(Tim[Ria], R[Ria]);
}
}
return 0;
}

唱、跳、rap 和篮球

假如我们知道四种同学的人数分别为\(A,B,C,D\)(和为\(n\)),求合法的序列数我们可以容斥.则有: \[ \sum_{i=0}^{\min(A,B,C,D)}(-1)^i\frac{n!}{(A-i)!(B-i)!(C-i)!(D-i)!}f[n][i] \] \(f[n][i]\)表示有\(n\)个人有\(i\)个位置的同学在讨论\(\text{cxk}\).

然后我们就有了一个\(O(n^5)\)的暴力: \[ \begin{aligned}&\sum_{A=0}^a\sum_{B=0}^b\sum_{C=0}^c\sum_{D=0}^d[A+B+C+D=n]\sum_{i=0}^{\min(A,B,C,D)}(-1)^i\frac{n!}{(A-i)!(B-i)!(C-i)!(D-i)!}f[n][i]\\=&\sum_{i=0}^{\frac{n}{4}}(-1)^if[n][i]\sum_{A=i}^a\sum_{B=i}^b\sum_{C=i}^c\sum_{D=i}^d[A+B+C+D=n]\frac{n!}{(A-i)!(B-i)!(C-i)!(D-i)!}\end{aligned} \] 对于每一个\(i\)设生成函数: \[ F(x)=\sum_{j=i}^n\frac{1}{(j-i)!}x^j \] 后面那一坨东西就相当于\([x^n]F^4(x)\).

直接暴力卷积复杂度\(O(n^3)\), 上\(\text{NTT}\)复杂度就是\(O(n^2\log n)\).听说还可以\(O(n^2)\).(不会不会不会)

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
/*
* 5510.cpp
* This file is part of 5510
*
* Copyright (C) 2019 - ViXbob
*
* 5510 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 5510 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 5510. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e3 + 5;
const int P = 998244353;

int a, b, c, d, n, fac[maxn], f[maxn][305], ifac[maxn];
int g[maxn], h[maxn], ans;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}
inline int C(int n, int m) { return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P; }

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); a = read(); b = read(); c = read(); d = read();
fac[0] = 1;
rep(i, 1, n) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[n] = inv(fac[n]);
dep(i, n - 1, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
rep(i, 0, n) {
f[i][0] = 1;
rep(j, 1, i / 4) f[i][j] = pls(f[i - 1][j], f[i - 4][j - 1]);
}
rep(s, 0, n / 4) {
memset(g, 0, sizeof(g));
memset(h, 0, sizeof(h));
int tmp = 0;
rep(i, s, a) rep(j, s, min(n - i, b)) g[i + j] = pls(g[i + j], 1ll * ifac[i - s] * ifac[j - s] % P);
rep(i, s, c) rep(j, s, min(n - i, d)) h[i + j] = pls(h[i + j], 1ll * ifac[i - s] * ifac[j - s] % P);
rep(i, 0, n) tmp = pls(tmp, 1ll * g[i] * h[n - i] % P);
if(s & 1) ans = dec(ans, 1ll * f[n][s] * tmp % P * fac[n - 4 * s] % P);
else ans = pls(ans, 1ll * f[n][s] * tmp % P * fac[n - 4 * s] % P);
}
/*
rep(i, 0, a) rep(j, max(n - i - c - d, 0), min(n - i, b))
rep(k, max(n - i - j - d, 0), min(n - i - j, c))
rep(l, max(n - i - j - k, 0), min(n - i - j - k, d)) {
int tmp = 0;
rep(z, 0, min(min(i, j), min(k, l)))
if(z & 1) tmp = dec(tmp, 1ll * fac[n - 4 * z] * f[n][z] % P * ifac[i - z] % P * ifac[j - z] % P * ifac[k - z] % P * ifac[l - z] % P);
else tmp = pls(tmp, 1ll * fac[n - 4 * z] * f[n][z] % P * ifac[i - z] % P * ifac[j - z] % P * ifac[k - z] % P * ifac[l - z] % P);
ans = pls(ans, tmp);
// ans = pls(ans, 1ll * fac[n] * ifac[i] % P * ifac[j] % P * ifac[k] % P * ifac[l] % P);
// cerr << i << " " << j << " " << k << " " << l << endl;
}
*/
cout << ans << endl;
return 0;
}
/*

1 1 1 1
2 1 1 0
2 0 1 1
2 1 0 1

*/

大中锋的游乐场

直接记状态\(dis[i][j]\)表示停在第\(i\)个点两种物品的差值为\(j\)(\(j\)可以小于零)的最短路.

然后直接\(\text{Dijkstra}\)就好了.

代码:

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
/*
* 5511.cpp
* This file is part of 5511
*
* Copyright (C) 2019 - ViXbob
*
* 5511 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 5511 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 5511. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e4 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const int del = 10;

int CASE, n, m, k, type[maxn], dis[maxn][25], S, T;
vector<pair<int, int> > G[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

inline void Dijkstra() {
priority_queue<pair<int, pair<int, int> > > q;
memset(dis, 0x3f, sizeof(dis));
q.push(mp(dis[S][type[S] + del] = 0, mp(S, type[S])));
while(q.size()) {
int u = q.top().second.first, d = q.top().second.second, now = -q.top().first; q.pop();
if(dis[u][d + del] != now) continue;
for(auto v : G[u]) {
if(abs(type[v.first] + d) <= k && dis[v.first][d + type[v.first] + del] > now + v.second) {
dis[v.first][d + type[v.first] + del] = now + v.second;
q.push(mp(-dis[v.first][d + type[v.first] + del], mp(v.first, d + type[v.first])));
}
}
}
int ans = *min_element(dis[T], dis[T] + del * 2);
cout << (ans == inf ? -1 : ans) << endl;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
CASE = read();
while(CASE--) {
n = read(); m = read(); k = read();
rep(i, 1, n) type[i] = (read() == 1 ? 1 : -1);
rep(i, 1, n) G[i].clear();
rep(i, 1, m) {
int x = read(), y = read(), w = read();
G[x].pb(mp(y, w)); G[y].pb(mp(x, w));
}
S = read(); T = read();
if(k == 0) { puts("-1"); continue; }
Dijkstra();
}
return 0;
}

甲苯先生和大中锋的字符串

\(\text{SAM}\)模板题?

\(\text{SAM}\)建出来以后,对于每个节点直接将\([\text{minlen,maxlen}]\)都加一,然后取最大的那个就好了.

加一的操作差分一下就好了.

代码:

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
/*
* 5512.cpp
* This file is part of 5512
*
* Copyright (C) 2019 - ViXbob
*
* 5512 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 5512 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 5512. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 15;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const int maxm = maxn << 1;

int T, k, n;
char s[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

struct SAM {
int fa[maxm], ch[maxm][26], maxlen[maxm], size[maxm], lst, cnt, deg[maxm], d[maxm];

SAM() { lst = cnt = 1; }

inline void clear(int n) {
lst = cnt = 1;
memset(fa, 0, sizeof(int) * (n + 5));
memset(ch, 0, sizeof(int) * (n + 5) * 26);
memset(deg, 0, sizeof(int) * (n + 5));
memset(d, 0, sizeof(int) * (n + 5));
memset(maxlen, 0, sizeof(int) * (n + 5));
memset(size, 0, sizeof(int) * (n + 5));
}

inline int Extend(int c) {
int cur = ++cnt, p = lst; size[cur] = 1;
maxlen[cur] = maxlen[p] + 1;
for( ; p && !ch[p][c]; p = fa[p]) ch[p][c] = cur;
if(!p) fa[cur] = 1;
else {
int q = ch[p][c];
if(maxlen[q] == maxlen[p] + 1) fa[cur] = q;
else {
int clone = ++cnt;
maxlen[clone] = maxlen[p] + 1;
memcpy(ch[clone], ch[q], sizeof(ch[q]));
fa[clone] = fa[q]; fa[q] = fa[cur] = clone;
for( ; p && ch[p][c] == q; p = fa[p]) ch[p][c] = clone;
}
} return (lst = cur);
}

inline void PreSolve() {
queue<int> q;
rep(i, 2, cnt) deg[fa[i]]++;
rep(i, 2, cnt) if(!deg[i]) q.push(i);
while(q.size()) {
int u = q.front(); q.pop();
size[fa[u]] += size[u];
if(!--deg[fa[u]]) q.push(fa[u]);
}
}

inline int calc() {
rep(i, 2, cnt) if(size[i] == k) d[maxlen[fa[i]] + 1]++, d[maxlen[i] + 1]--;
rep(i, 1, n) d[i] += d[i - 1];
int ans = -1, Mx = 0;
dep(i, n, 1) if(d[i] > Mx) Mx = d[i], ans = i;
return ans;
}
} sam;

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
T = read();
while(T--) {
scanf("%s%d", s + 1, &k);
n = strlen(s + 1);
sam.clear(2 * n);
rep(i, 1, n) sam.Extend(s[i] - 'a');
sam.PreSolve();
printf("%d\n", sam.calc());
}
return 0;
}

甲苯先生的线段树

神仙题..还是道原题...

第一问因为树高是\(\log\)级别的,所以直接暴跳父亲就好了.设求出来的和为\(S\).

对于第二问我们考虑链上枚举深度最低的点\(x\)\(x\)的左右儿子的的链的深度为\(L,R\).(\(L,R\)为零表示没有左儿子或者右儿子). 记做三元组\((x,L,R)\).

这个对于每个三元组\((x,L,R)\)的编号和的下界为: \[ \begin{aligned}&x+2x\sum_{i=0}^{L-1}2^i+(2x+1)\sum_{i=0}^{R-1}2^i\\=&2x(2^L-1)+(2x+1)(2^R-1)+x\\=&2^{L+1}x-3x+2^{R+1}x+2^R-1\end{aligned} \] 对于一条长度为\(n\)的左链(即这条链上的所有点都是父亲节点的左儿子),自底向上,的第\(i\)个节点如果变成了右儿子,那么这个节点会带来独立的贡献\(\sum_{j=0}^{i-1}2^j=2^i-1\).

那么对于每个三元组\((x,L,R)\)的编号和的上界为: \[ \begin{aligned}&2^{L+1}x-3x+2^{R+1}x+2^R-1+\sum_{i=1}^{L-1}2^i-1+\sum_{i=1}^{R-1}2^i-1\\=&2^R-1+(2^{L+1}+2^{R+1}-3)x+(2^L-2-(L-1))+(2^R-2-(R-1))\\=&2^{R+1}+2^L-3-L-R+(2^{L+1}+2^{R+1}-3)x\end{aligned} \] 然后我们又发现\((x,L,R)\)的上界都小于\((x+1,L,R)\)的下界: \[ 2^{R+1}+2^L-3-L-R<2^R-1+2^{L+1}+2^{R+1}-3 \] 所以对于每个二元组\((L,R)\),\(x\)只能等于: \[ \left\lfloor\frac{S-2^R+1}{2^{L+1}+2^{R+1}-3}\right\rfloor \] 所以我们就是要找到一个合理的分配左右儿子的方式使得编号和为\(S-x(2^{L+1}+2^{R+1}-3)-2^R+1\).

这个东西可以用复杂度正确的\(O(d^5)\)的数位\(\text{dp}\).但是很神奇的是打个爆搜(用\(\text{unordered}\_\text{map}\)记一下状态)却跑得飞快.(黑人问号???)

但是好像\(O(d^5)\)跑十组数据还是不太星啊???所以我很好奇\(\text{std}\)是怎么打的....

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
/*
* 5513.cpp
* This file is part of 5513
*
* Copyright (C) 2019 - ViXbob
*
* 5513 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 5513 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 5513. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

int T;
ll d, a, b, c, k, S, mi[maxn], ans;
unordered_map<ll, ll> f[55][55];

inline ll read() {
char ch = getchar(); ll u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

inline ll dfs(int L, int R, ll S) {
if(S < 0) return 0;
if(L <= 0 && R <= 0) return S == 0;
if(mi[L + 1] - L - 2 + mi[R + 1] - R - 2 < S) return 0;
if(L < R) swap(L, R);
if(f[L][R].count(S)) return f[L][R][S];
return f[L][R][S] = dfs(L - 1, R, S) + dfs(L - 1, R, S - mi[L] + 1);
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
T = read(); mi[0] = 1;
rep(i, 1, 50) mi[i] = mi[i - 1] << 1;
while(T--) {
d = read(); a = read(); b = read(); c = read();
int la = 63 - __builtin_clzll(a), lb = 63 - __builtin_clzll(b);
S = ans = 0;
if(la < lb) swap(a, b), swap(la, lb);
while(la != lb && a != b) S += a, a >>= 1, la--;
while(a != b) S += a + b, a >>= 1, b >>= 1;
S += a;
if(c == 1) printf("%lld\n", S);
else {
rep(i, 0, d - 1) rep(j, 0, d - 1) if(mi[i + 1] + 3 * mi[j] - 4 <= S) {
ll x = (S - mi[j] + 1) / (mi[i + 1] + mi[j + 1] - 3);
if((int)log2(x + 0.1) + 1 + max(i, j) > d) continue;
ans += dfs(i - 1, j - 1, S - mi[j] + 1 - x * (mi[i + 1] + mi[j + 1] - 3));
}
printf("%lld\n", ans - 1);
}
}
return 0;
}