从这里开始
小结
这次练习，感觉自己存在很多细节的问题。
比如，前3个题很搞笑，被罚了4次时（A题是写了假贪心，B题是忘了条件，C题是忽略细节）。同时时间也安排的不是很好，比如F题的代码很长，但是我先去写了F，再去写G题，到时Penalty再度变高。
还有件有趣的事，切完D题，输地址时输成了F题（大概是我字母表背得有点"好"），成功跳过E题。
最后看E题，没仔细看读入，发现样例有毒，手算始终不对。时间再度-10min。
最后比较悲催的是H和I根本没时间看。虽然估计看了也做不起。
唯一感到比较欣慰的是多年做cf的题，英语水平有提升（大概是一场比赛题面的单词本来就不多），基本不用翻译就能读懂题目。
-->
Problem A Diagonal Walking
题目大意
给定一个只包含'U'和'R'的字符串，你可以将"RU"或者'UR"替换为"D"。问能使串长能变成的最小值。
直接把 RU 或者 UR 替换为 D 即可。
Code
/**
* Codeforces
* Problem#954A
* Accepted
* Time: 31ms
* Memory: 0k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; int n;
char s[233]; int main() {
scanf("%d", &n);
scanf("%s", s + 1);
int ans = n;
for (int i = 1; i < n; i++) {
if (s[i] ^ s[i + 1]) {
i++, ans--;
continue;
}
}
printf("%d\n", ans);
return 0;
}
Problem B String Typing
题目大意
有一台打字机，要输入1个字符串，有两种操作：
- 向末尾输入一个字符
- 将当前输入的字符串复制一遍粘在后面
操作2只能使用1次。问最少的操作次数。
没看到只能用1次，傻傻地写了个dp。并成功获得了：
然后急急忙忙去加个状态。
其实只能用1次直接贪心就好了。当减少的操作次数最多的时候用操作2.
Code
/**
* Codeforces
* Problem#954B
* Accepted
* Time: 31ms
* Memory: 0k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; int n;
char str[];
int f[][]; inline void init() {
scanf("%d", &n);
scanf("%s", str + );
} boolean equal(int l1, int l2, int len) {
for (int i = ; i < len; i++)
if (str[l1 + i] != str[l2 + i])
return false;
return true;
} inline void solve() {
f[][] = ;
for (int i = ; i <= n; i++) {
f[i][] = f[i - ][] + ;
f[i][] = f[i - ][] + ;
if (!(i & ) && (equal(, (i >> ) + , i >> )))
f[i][] = min(f[i][], f[i >> ][] + );
}
printf("%d\n", min(f[n][], f[n][]));
} int main() {
init();
solve();
return ;
}
Problem B
Problem C Matrix Walk
题目大意
有一个$x\times y$的网格图，但是不知道$x, y$的值。规定$i$行$j$列的格子的标号为$(i - 1)y + j$。
给定一个长度为$n$的经过的格子序列，规定只能走相邻的格子，且不能走出边界，也不能停留在同一个格子。问是否可能存在一组$x, y$使得路径合法，如果存在，输出这一组。
找最大的一组相邻的差作为$y$。
$x$足够大就好了（为什么？因为没影响）。
然后代进去检验是否合法。
Code
/**
* Codeforces
* Problem#954C
* Accepted
* Time: 61ms
* Memory: 800k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; int n;
int *ar; inline void init() {
scanf("%d", &n);
ar = new int[(n + )];
for (int i = ; i <= n; i++)
scanf("%d", ar + i);
} int mxd = ;
set<int> s;
void termin() {
puts("NO");
exit();
} inline void solve() {
for (int i = ; i < n; i++) {
int dif = abs(ar[i + ] - ar[i]);
if (!dif)
termin();
if (mxd > && dif > && dif != mxd)
termin();
if (dif > )
mxd = dif;
} int ly = ar[] % mxd;
if (!ly) ly = mxd;
int lx = (ar[] - ly) / mxd + ;
for (int i = , cx, cy; i <= n; i++) {
cy = ar[i] % mxd;
if (!cy) cy = mxd;
cx = (ar[i] - cy) / mxd + ;
if (abs(cx - lx) + abs(cy - ly) != )
termin();
lx = cx, ly = cy;
}
puts("YES");
printf("%d %d", , mxd);
} int main() {
init();
solve();
return ;
}
Problem C
Problem D Fight Against Traffic
题目大意
给定$n$个点$m$条边的无向连通简单图。每条边边权均为1。
要求加一条原本不存在的边，使得新图没有自环，$s, t$之间的距离不改变。
问方案数。
看这数据范围挺小的。
分别跑出$s, t$的最短路径生成树。
然后枚举边的两个端点，判断加入后新产生的路径长度是否合法。
Code
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; const int N = 1e3 + ; int n, m, s, t;
boolean g[N][N];
int f1[N], f2[N]; inline void init() {
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = , u, v; i <= m; i++) {
scanf("%d%d", &u, &v);
g[u][v] = true, g[v][u] = true;
}
} typedef class Node {
public:
int p, dis; Node(int p = , int dis = ):p(p), dis(dis) { } boolean operator < (Node b) const {
return dis > b.dis;
}
}Node; priority_queue<Node> que;
void dijstra(int s, int* f) {
memset(f, 0x7f, sizeof(int) * (n + ));
que.push(Node(s, f[s] = ));
while (!que.empty()) {
Node e = que.top();
que.pop();
if (e.dis != f[e.p])
continue;
for (int i = ; i <= n; i++)
if (g[e.p][i] && e.dis + < f[i])
que.push(Node(i, f[i] = e.dis + ));
}
} int ans = ;
inline void solve() {
dijstra(s, f1);
dijstra(t, f2);
for (int i = ; i <= n; i++)
for (int j = i + ; j <= n; j++)
if (!g[i][j] && f1[i] + f2[j] + >= f1[t] && f1[j] + f2[i] + >= f1[t])
ans++;
printf("%d", ans);
} int main() {
init();
solve();
return ;
}
Problem D
Problem E Water Taps
题目大意
给定$n, T, a_{i}, t_{i}$，找出一组$x_{i}$满足$0\leqslant x_{i} \leqslant a_{i}$，且$\frac{\sum_{i = 1}^{n}x_{i}t_{i}}{\sum_{i = 1}^{n}x_{i}} = T$。问$\sum_{i = 1}^{n}x_{i}$的最大值。无解输出0。
好像一群人直接贪心。表示考场上没想出纯贪心。
Virtual Contest中看完题，觉得可以用函数搞一搞。
考虑如果设$D = \sum_{i = 1}^{n}x_{i}$，那么设$f(D), g(D)$分别是$\sum_{i = 1}^{n}x_{i}t_{i}$的最小值和最大值。
然后猜想$[f(D), g(D)]$之间的一切实数都可以被$\sum_{i = 1}^{n}x_{i}t_{i}$凑出来。
然后表示智商不够，不会证明。日后会了补上。
至于$f(D), g(D)$显然可以用贪心来求。画出来的图像大概是这样的：
当$y = T\times D$被另两函数夹在中间的时候都是合法的。因此我们可以求在第一象限内的两个交点。求出来之后就可以算答案了。
于是便有了二分答案 + 贪心的做法。然后我也不知道发生了什么：
然后我改成函数求交：
有毒。
-->
移项，排序后贪心即可。
Code
/**
* Codeforces
* Problem#954E
* Accepted
* Time: 93ms
* Memory: 4400k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; const int N = 2e5 + 5; #define ll long long
#define pii pair<int, int> int n, T;
ll sum = 0;
int a[N];
vector<pii> vL, vR; int main() {
scanf("%d%d", &n, &T);
double ans = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
ans += a[i];
}
for (int i = 1, t; i <= n; i++) {
scanf("%d", &t);
sum += 1ll * a[i] * (t - T);
if (t <= T) {
vL.emplace_back(T - t, a[i]);
} else {
vR.emplace_back(t - T, a[i]);
}
}
if (sum < 0) {
sum = -sum;
} else {
vL = vR;
}
sort(vL.begin(), vL.end(), greater<pii>());
for (auto e : vL) {
if (!sum)
break;
ll tmp = 1ll * e.first * e.second;
if (tmp > sum) {
ans -= 1.0 * sum / e.first;
break;
} else {
sum -= tmp;
ans -= e.second;
}
}
printf("%.9lf\n", ans);
return 0;
}
Problem F Runner's Problem
题目大意
给定一个$3\times m$的棋盘，在$(2, 1)$的地方有一个棋子，棋子每次只能移动到下一列的相邻的行或者当前行。
棋盘上有$n$段障碍，第$i$段障碍是在第$a_{i}$行的$l_{i}$列到第$r_{i}$列。棋子不能到障碍格上。
问棋子从$(2, 1)$到$(2, m)$的方案数。（答案模$10^{9} + 7$）
随便写写dp方程，把转移表变成矩阵。跑快速幂。
Code
/**
* Codeforces
* Problem#954F
* Accepted
* Time: 390ms
* Memory: 1700k
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; #define ll long long
#define pli pair<ll, int> typedef class Segment {
public:
ll l, r;
int sta; Segment() { }
Segment(ll l, ll r, int sta):l(l), r(r), sta(sta) { }
}Segment; const int M = 1e9 + ; typedef class Matrix {
public:
int r, c;
int a[][]; Matrix(int r = , int c = ):r(r), c(c) {} Matrix operator * (Matrix b) {
Matrix rt(r, b.c);
assert(c == b.r);
for (int i = ; i < r; i++)
for (int j = ; j < b.c; j++) {
rt[i][j] = ;
for (int k = ; k < c; k++)
rt[i][j] = (rt[i][j] + a[i][k] * 1ll * b[k][j]) % M;
}
return rt;
} int* operator [] (int p) {
return a[p];
}
}Matrix; const int N = 3e4 + ; Matrix qpow(Matrix a, ll p) {
assert(p >= );
Matrix pa = a, rt(, );
for (int i = ; i < ; i++)
for (int j = ; j < ; j++)
rt[i][j] = (i == j);
for ( ; p; p >>= , pa = pa * pa)
if (p & )
rt = rt * pa;
return rt;
} int n;
ll m;
pli ad[N], rm[N];
Segment ss[N]; inline void init() {
scanf("%d"Auto, &n, &m);
int a;
ll l, r;
for (int i = ; i <= n; i++) {
scanf("%d"Auto""Auto, &a, &l, &r);
ad[i].first = l, ad[i].second = a - ;
rm[i].first = r + , rm[i].second = a - ;
}
} Matrix mktrans(int os, int ns) {
Matrix rt(, );
for (int i = ; i < ; i++)
for (int j = ; j < ; j++)
rt[i][j] = (abs(i - j) <= && !(os & ( << i)) && !(ns & ( << j)));
return rt;
} int ts[], tp = ;
inline void solve() {
sort(ad + , ad + n + );
sort(rm + , rm + n + );
int ca = , cb = ;
ll st = , ed;
while (ca <= n || cb <= n) {
while (ca <= n && ad[ca].first == st)
ts[ad[ca].second]++, ca++;
while (cb <= n && rm[cb].first == st)
ts[rm[cb].second]--, cb++; int sta = ;
for (int i = ; i < ; i++)
if (ts[i])
sta |= ( << i); ed = m + ;
if (ca <= n)
ed = ad[ca].first;
if (cb <= n)
ed = min(ed, rm[cb].first);
ss[++tp] = Segment(st, ed - , sta);
st = ed;
} Matrix f(, );
f[][] = f[][] = , f[][] = ;
Matrix T = mktrans(ss[].sta, ss[].sta);
f = f * qpow(T, ss[].r - ss[].l);
// cerr << f[0][0] << " " << f[0][1] << " " << f[0][2] << endl;
for (int i = ; i <= tp; i++) {
T = mktrans(ss[i - ].sta, ss[i].sta);
f = f * T;
T = mktrans(ss[i].sta, ss[i].sta);
f = f * qpow(T, ss[i].r - ss[i].l);
// cerr << ss[i].l << " " << ss[i].r << endl;
// cerr << f[0][0] << " " << f[0][1] << " " << f[0][2] << endl;
}
printf("%d\n", f[][]);
} int main() {
init();
solve();
return ;
}
Problem F
Problem G Castle Defense
题目大意
有片城墙被分为$n$个防守段。第$i$段有$a_{i}$个弓箭手。定义一段防守段的防御力是距离它的距离不超过$r$的所有防守段的弓箭手数量之和。定义这片城墙的稳定程度是每个防守段的防御力的最小值。
现在有$k$个后备弓箭手，你可将他们分配任何防守段，但不能调动原有的弓箭手。问调动后最大的稳定程度。
显然二分答案。
考虑怎么check。对于一个防御值小于$mid$的防守段$i$，能对它产生贡献的一些防守段中分配的后备弓箭手总数不得小于$mid - def[i[$。
然后设在第$i$个防守段设置的弓箭手数量为$a_{i}$，对它求一个前缀和$s$。
显然使用差分约束，然后连边就很显然了：
- $s_{r} - s_{l - 1} \leqslant mid - def[i], (def[i] < mid)$
- $s[i]\leqslant s[i + 1]$
由于图比较特殊，不必用最短路算法。直接一个for，完事。
（感觉把防守段替换为烽火台食用更佳，总之原题说的是section，实在不知道怎么翻译比较好）。
Code
/**
* Codeforces
* Problem#954G
* Accepted
* Time: 358ms
* Memory: 13700k
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; #define ll long long const int N = 5e5 + ; int n, r;
ll k;
int ar[N];
ll ps[N], def[N];
ll f[N]; inline void init() {
scanf("%d%d"Auto, &n, &r, &k);
for (int i = ; i <= n; i++)
scanf("%d", ar + i);
for (int i = ; i <= n; i++)
ps[i] = ps[i - ] + ar[i];
} boolean check(ll mid) {
memset(f, , sizeof(f));
for (int i = ; i <= n; i++) {
f[i] = max(f[i - ], f[i]);
if (def[i] >= mid)
continue;
int l = max(i - ::r, ), r = min(i + ::r, n);
f[r] = max(f[l - ] + mid - def[i], f[r]);
}
return f[n] <= k;
} inline void solve() {
for (int i = ; i <= n; i++) {
int l = max(i - ::r, ), r = min(i + ::r, n);
def[i] = ps[r] - ps[l - ];
} ll l = , r = 2e18;
while (l <= r) {
ll mid = (l + r) >> ;
if (check(mid))
l = mid + ;
else
r = mid - ;
}
printf(Auto, l - );
} int main() {
init();
solve();
return ;
}
Problem G
Problem H Path Counting
题目大意
给定一棵深度为$n$的树，根节点的深度为1，深度为$i$的点的度数为$a_{i}$，保证$a_{n} = 0$。要求对于每个$1\leqslant d \leqslant 2n - 2$，输出长度为$d$的简单无向路径数量对模$10^9 + 7$的剩余。
现在说一下一个非常常见的计数对象：取路径的最高点。
发现每个深度的每个子树的情况完全相同，因此只需要对每个深度$i$计算答案，然后乘上一个常数$c_{i}$。
设$g_{i,d}$表示在深度为$i$的一个子树中，距离根节点$d$条边的点的数量。
那么有：
$ans_{d} = \sum_{i = 1}^{n}\left[g_{i, d} + \left(\sum_{j = 1}^{\left \lfloor d/2 \right \rfloor}g_{i + 1, j - 1}\cdot g_{i +1, d - j - 1}\right )a_{i}(a_{i} - 1) - [2\mid d]g_{i + 1,d/2 - 1}^2 \right ]c_{i}$
然后来慢慢解释这个式子。
$g_{i, d}$是从当前点出发的路径数量，$中间求和是拼接两条路径，为了防止算重，选择两个不同的子树，并要求第一个子树选择的路径长度小于等于第二个子树中选择，当选择路径长度不同时，正反都可以，所以答案乘2，再减去选择路径长度相同的一部分的答案就行了。
然后开心地发现这个式子是三方的。
接着发现$g, c$都是可以直接算的：
$g_{i, d}=\prod_{j = 0}^{d - 1}a_{i + j}$
$c_{i} = \prod_{j = 1}^{i - 1}a_{j}$
中间的一坨求和式子可以看成，枚举任意$i$，然后在$i + 1$后面选择两段连续的$a$，两段都要包含$a_{i + 1}$，长度和为$d - 2$，再把这两段的积乘起来。
然后很容易发现，设$f_{i, d} = \sum_{j = 0}^{\left \lfloor d/2 \right \rfloor}g_{i, j}\cdot g_{i, d - j}$，那么算$f_{i + 1, d - 2}$的时候可以把$j = 0$的一部分先刨开，然后除以$a_{i}^{2}$就行了。
$f_{i + 1, d - 2} = (f_{i, d} - g_{i, d})a_{i}^{-2}$
于是这个zz做法可以实现$O(n^{2})$。常数贼大，跑得贼慢，sad。。。
然后看了看标算。标算取路径两端点作为计数点，这样每条路径会被计算2次，答案除以2就行了。对于以某个点为端点的路径可以分成两种，第一种是向上走（子树外），第二种是向下走（子树内）。第二部分显然，第一部分转移考虑它走到父节点后的方向，时间复杂度一样，但常数小很多。
/**
* Codeforces
* Problem#954H
* Accepted
* Time: 1544ms
* Memory: 200k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; const int N = , M = 1e9 + ; void exgcd(int a, int b, int& x, int& y) {
if (!b)
x = , y = ;
else {
exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
} int inv(int a, int n) {
int x, y;
exgcd(a, n, x, y);
return (x < ) ? (x + n) : (x);
} int n;
int inv2 = (M + ) >> ;
int ar[N], br[N];
int pro[N];
int ans[N << ];
int f[][N << ]; int add(int a, int b) {
a += b;
if (a >= M)
a -= M;
return a;
} int sub(int a, int b) {
a -= b;
if (a < )
a += M;
return a;
} inline void init() {
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%d", ar + i);
ar[n] = ;
for (int i = ; i <= n; i++)
br[i] = inv(ar[i], M);
} int pow2(int x) {
return x * 1ll * x % M;
} inline void solve() {
int cur = , nxt = , P = ;
pro[] = ;
for (int i = ; i <= n; i++)
pro[i] = pro[i - ] * 1ll * ar[i] % M;
f[cur][] = ;
for (int d = ; d <= ((n - ) << ); d++)
for (int i = max(, d - n); i <= n && i <= d && i <= d - i; i++)
f[cur][d] = add(f[cur][d], pro[i] * 1ll * pro[d - i] % M);
for (int i = ; i < n; i++) {
if (i > ) {
pro[] = ;
for (int j = ; i + j <= n; j++)
pro[j + ] = pro[j] * 1ll * ar[i + j] % M;
}
for (int d = , x, C; d <= ((n - i) << ); d++) {
x = ((d <= n - i) ? (pro[d]) : ());
C = ar[i] * 1ll * (ar[i] - ) % M * P % M;
f[nxt][d - ] = sub(f[cur][d], x) * 1ll * br[i] % M * 1ll * br[i] % M;
ans[d] = add(ans[d], f[nxt][d - ] * 1ll * C % M);
if (!(d & ))
ans[d] = sub(ans[d], pow2(pro[d >> ] * 1ll * br[i] % M) * 1ll * C % M * inv2 % M);
}
for (int d = ; d <= n - i; d++)
ans[d] = add(ans[d], pro[d] * 1ll * P % M);
P = P * 1ll * ar[i] % M;
swap(cur, nxt);
} for (int i = ; i <= (n - ) << ; i++)
printf("%d ", ans[i]);
} int main() {
init();
solve();
return ;
}
Problem H
Problem I Yet Another String Matching Problem
题目大意
定义一个操作是将串内的一种字符改成另一种字符。定义两个串的编辑距是使得这两个串相等的最少操作数。
给定两个串$S, T\ \ \left(|S|\leqslant |T|\right)$，询问$S$的每个串长等于$|T|$的子串和$|T|$的编辑距。字符集 'a' ~ 'f'
进行一种操作相等于让两种字符等价。这样我们可以将1次操作看作在无向图中将两个字符连接起来。
考虑对于$S_{i} \neq T_{j}$，那么$S_{i}$需要和$T_{j}$等价，那么在无向图中连一条边。答案是字符集大小减去连通块个数。
然后讲标算。标算比较套路，注意到边的数量不超过30条，因此想办法判断每条边在每一次询问中是否存在。
考虑枚举这条边$(a, b)$，将$S$出现$a$的地方标为1，将$T$出现$b$的地方也标为1。如果$S_{i} = a \wedge T_{j} = b$，那么以$i - j$作为起点的地方就会存在这样一条边。
然后就是套路了，翻转串$T$，原来的$j$变为了$|T| - j$，贡献的位置就是$|T| + i - j$，然后跑FFT算答案。
剩下的就是暴力了。可以dfs，也可以dsu算连通块的个数。
由于我很懒，不想写FFT，就成了可恶的嘴巴AC选手。
然后来膜一下Execution Time榜rk 1同学的Hash做法。
考虑按顺序枚举$S$的每个子串$S'$，注意到我们只关心连通块的个数。
不幸的是我们暂时不能区分多个连通块，但是我们有办法当前的连通子图不是极大的情况。
由于字符集很小，我们可以尝试暴力枚举一个连通块由哪些字符组成。考虑选择了一个非极大连通子图，那么存在一个点有一条边连向另一个字符。
因此这个选定的字符集在$S'$中出现的所有位置和$T$中出现的所有位置不相同。因此通过判断出现位置的集合是否相同可以判断非极大连通子图。
如何判断选定的字符集是否连成一个连通块？我们按照字符集包含的字符个数的顺序来枚举，然后对于找的一个极大连通子图，我们把些字符ban掉。这样就能保证了。
判断出现位置集合是否相同可以用Hash，每做完一个询问更新一下位置集合的Hash值。
好像还有一个神奇的dfs做法？没看懂。qwq
口胡另一个做法，考虑最多有 $|\Sigma|$ 条边，可以用 Hash 表示出每一种字符出现的所有位置，即 $h_c(s) = \sum_{i = 0}^{|s| - 1} x^i [s_i = c]$。用并查集维护已经有的边形成的连通块。考虑用二分求出下一对不同的字符，每次求每个字符的 Hash 值乘上它的所在连通块的根的标号。 可以做到 $O(n|\Sigma|^2 \log n)$ 或者 $O(nB_{|\Sigma|} + n|\Sigma|\log n)$
Code
/**
* Codeforces
* Problem#954I
* Accepted
* Time: 62ms
* Memory: 1200k
*/
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
typedef bool boolean; #define ull unsigned long long const int N = , S = << ;
const ull base = ; int n, m;
char sa[N], sb[N];
ull pow7[N];
ull ps[S], pt[S];
int bit[S], sta[S]; inline void init() {
scanf("%s%s", sa, sb);
n = strlen(sa), m = strlen(sb);
pow7[] = ;
for (int i = ; i < n; i++)
pow7[i] = pow7[i - ] * base;
} void update(ull *ar, int c, ull val, int sgn) {
int temp = ( << c);
for (int s = temp; s < S; s = (s + ) | temp)
ar[s] += val * sgn;
} boolean cmp(const int& a, const int& b) {
return bit[a] < bit[b];
} inline void prepare() {
bit[] = ;
for (int i = ; i < S; i++)
bit[i] = bit[i - (i & (-i))] + ;
for (int i = ; i < S; i++)
sta[i] = i;
sort(sta, sta + S, cmp);
} inline void solve() {
for (int i = ; i < m; i++)
update(ps, sa[i] - 'a', pow7[i], );
for (int i = ; i < m; i++)
update(pt, sb[i] - 'a', pow7[i], ); for (int i = ; i <= n - m; i++) {
int ban = , res = ;
for (int j = ; j < S; j++) {
int s = sta[j];
if (!(s & ban)) {
if (!ps[s] && !pt[s])
ban |= s;
else if (pt[s] * pow7[i] == ps[s]) {
res += bit[s] - ;
ban |= s;
}
}
}
printf("%d ", res);
if (i + m < n) {
update(ps, sa[i] - 'a', pow7[i], -);
update(ps, sa[i + m] - 'a', pow7[i + m], );
}
}
} int main() {
init();
prepare();
solve();
return ;
}
Problem I