8.14
T1
简单贪心，照着题意模拟即可。
T2
给一棵树，有点权与边权，定义一棵子树 \(f(x)\) 为子树里权值为 \(x\) 的点两两距离和，并给定 \(k_i\)，求以 \(i\) 为根的子树里满足 \(f(x)\) 最大的 \(x\) 与 \(i\) 的子树里编号 \(k_i\) 小的 \(y\) 的 \(f(y)\)。
那么借助转移数组，用 $ g(x,i) $ 去表示我们 \(i\) 子树的所有权值为 \(x\) 的点到点 \(i\) 的距离和，而 $ h(x,i) $ 为 \(i\) 子树里权值为 \(x\) 的点的数目。
随便搞个数据结构去维护所有出现过的权值的 \(f,h,g\) 三个数组，自底向上地启发式合并。那么就只需要考虑如何用点 \(v\) 去更新父节点 \(u\) 的信息。
我们记录 $ f'(x,u) $ 为 \(v\) 并入之前的 $ f(x,u) $ ，$ g',h' $ 同理。
就会有
\[h(x,u)=h'(x,u)+h(x,v); \\ g(x,u)=g'(x,u)+g(x,v)+h(x,v)\times w(u,v); \\ f(x,u)= f'(x,u)+g'(x,u)\times h(x,v)+h'(x,u)\times (g(x,v)+h(x,v)\times w(u,v)); \]直接查询就行。
T3
萌萌结论题，不能被 \(ax+by\) 表示的数有 $ \frac{(a-b)(b-1)}{2} $ 个，并且最大不能被表示的数为 $ a*b-a-b $，然后用枚举的思想去找接近的项即可。
8.15
T1
牛逼的多项式，给你一个 \(n\) 维的多维体去在表面刷漆求表面被刷了 \(i\) 层漆的块分别有几个。也就是三维的一个立方体表面刷一层色，求刷了 \(i\) 层色的立方体的个数的高维度版本。
这里给出每一维度的边长 \(a_i\)。
那么分类讨论， \(a_i=1\)，所有的小锥体都只会增加染色面，两个面变为了锥体。
而 $a_i \ge 2 $ 时，会发现只有两边的小锥体会增加一个染色面，中间的虽然也会增加两个面但是并不会染色，所以染色面不变。
可以分别得到式子 \(x^2\),\(2x+(a_i-2)\)
NTT就行。
T2
李超树简单题，开值域树然后直接覆盖就行。
注意操作不均衡，我们用分块去优化一下即可。
也就是对于单点修改直接插入李超树，而区间修改用分块维护，便于操作。
T3
神仙期望，题意难懂，咕咕咕
9.1
T1
给你 \(n\) 个人围成圈，每个人手里分别 \(a_i\) 个球，每个人可以选择手里 $ 0-a[i]$ 个球传递向右手边的那个人，把每个可能产生的新序列设为 \(S\)，求 \(\sum\Pi a_i\)，对\(998244353\)取模。
也就是对于每一种可能的序列求所有球个数的乘积再加起来。
那么就去分析性质，首先每个人给的球数量不同不代表最后序列不同。
如果每个人都会至少给出一个球，就可以让每个人都少给出相同的个数，效果也就会相同。所以至少会有一个人不传球，才会产生新的方案。
那么可以得到暴力DP式子 $ f(i,j) $ 表示第\(i\)个人给\(j\)个球的前缀乘积和，然后为了不重不漏，我们指定\(i\)是不给球的那个，并且指定他前面的人都必须给球。
\[f(j,k)=\sum\limits_{l=0}^{a_j-1} f(j-1,l)\times(a_j+l-k) \]最后答案是把所有的 \(f(i,0)\) 加起来。
考虑优化
\[f(j,k)=\sum\limits_{l=0}^{a_j-1} f(j-1,l) \times l+\sum\limits_{l=0}^{a_j-1}f(j-1,l)\times (a_j-k) \]那么求出来两项就可以完成转移，但是还是不能接受。
接着设 $ w(j)=\sum\limits_{l=0}^{a_j}f(j,l) $, $ g(j)=\sum\limits_{l=0}^{a_j}f(j,l)\times l,h_1(x)=\frac{(1+x)\times x}{2},h_2=\frac{x\times(x+1)\times(2x+1)}{6} $
可得到
\[w(j)=(a_j-[j<i]+1)(g(j-1)+a_jw(j-1))-h_1(a_j)w(j-1) \\ g(j)=h_1(a_j)(g(j-1)+a_jw(j-1))-h_2(a_j)w(j-1)\times l \]所以我们只需要累加 $ a_jw(i-1)+g(i-1) $，矩阵维护一下即可达到 \(o(n)\) 级别。
#define int long long
#define ll long long
#define Maxn 100010
const ll p = 998244353;
inline ll qp(int a, int b)
{
ll res = 1;
while (b)
{
if (b & 1)
res = 1ll * res * a % p;
a = 1ll * a * a % p;
b >>= 1;
}
return res;
}
const ll inv2 = qp(2, p - 2), inv6 = qp(6, p - 2);
int n;
ll a[Maxn], f[Maxn][2];
inline ll sum(ll x)
{
return x * (x + 1) % p * inv2 % p;
}
inline ll psum(ll x)
{
return x * (x + 1) % p * (x * 2 + 1) % p * inv6 % p;
}
inline int sol(int x, int o)
{
memset(f, 0, sizeof(f));
f[1][o]=1;
for (int i = 1; i <= n; i++)
{
f[i + 1][0] = (f[i + 1][0] + (sum(a[i] - x) * f[i][0] % p)) % p;
f[i + 1][1] = (f[i + 1][1] + (a[i] * sum(a[i]) % p - psum(a[i]) + p) % p * f[i][0] % p) % p;
f[i + 1][0] = (f[i + 1][0] + (a[i] + 1 - x) * f[i][1] % p) % p;
f[i + 1][1] = (f[i + 1][1] + (sum(a[i]) * f[i][1] % p)) % p;
}
return f[n + 1][o];
}
inline void work()
{
n = read();
for (int i = 1; i <= n; i++)
a[i] = read();
write(((sol(0, 0) + sol(0, 1)) % p - (sol(1, 0) + sol(1, 1)) % p + p) % p);
return dwd;
}
signed main()
{
work();
return 0;
}
T2
CF1470E。
T3
一个集合的装饰子集为不被其他任何数包含的子集， \(a\) 包含 \(b\) 当且仅当二进制下 \(b\) 为 \(1\) 的位上 \(a\) 也为 \(1\)。
那么考虑一下原序列的装饰子集 \(S\)，并且设 \(x\in S\)。那么 \(x\) 不被任何数包含，也就是说对于任意子串同样是不会被包含。所以 \(x\) 肯定是属于某个子集的装饰子集。
那么也就是说所有子串装饰子集等于 \(S\)。
我们用 \(l_i\) 表示让 \([l_i,i]\) 包含所有的 \(S\) 内元素的最大 \(l_i\) ，双指针求出即可。
直接DP, \(f_i\) 就表示 $ [1,i] $ 的答案，初始化为0。那么对于一个可能的 \(l_i\)，有 $ f(i)=\sum\limits_{j=0}^{l_i-1}f(j) $，也就表示了 \([j,i]\) 为合法子串。可以前缀和优化到 $O(n) $。
对于 \(S\)，直接求就行。
#define int long long
#define Maxn 3000010
const int p = 1e9 + 7;
const int Maxv = 1 << 21;
int n, cnt, sum;
int ansx;
int a[Maxn], sums[Maxn], t[Maxv];
int f[Maxn], T[Maxv], vis[Maxv];
inline void work()
{
n = read();
for (int i = 1; i <= n; i++)
a[i] = read(), t[a[i]] = vis[a[i]] = 1;
for (int LEN = 2; LEN <= Maxv; LEN <<= 1)
for (int i = 0, k = LEN / 2; i < (Maxv); i += LEN)
for (int j = 0; j < k; j++)
t[i + j] += t[i + j + k];
for (int i = 0; i < Maxv; i++)
vis[i] &= (t[i] == 1), sum += vis[i];
f[0] = sums[0] = 1;
for (int j = 1, i = 1; i <= n; i++)
{
if (vis[a[i]])
cnt += (T[a[i]] == 0), T[a[i]]++;
while (cnt == sum and (vis[a[j]] == 0 or T[a[j]] > 1))
{
if (vis[a[j]])
T[a[j]]--;
j++;
}
if (cnt == sum)
f[i] = sums[j - 1];
sums[i] = (sums[i - 1] + f[i]) % p;
}
write(f[n]);
return dwd;
}
signed main()
{
work();
return 0;
}
9.2
T1
模拟。
T2
就是一个必须经过P个点的最短路问题。比较暴力的一种方式是BFS，每次都去枚举下一步搜索哪个点，但是一大问题是搜索考虑了顺序问题，因此会有大量的无意义的搜索树，而我们只关心是否P个点全都经过。观察到P很小，所以采用状压的方法去表示还未经过的点，然后去更新。
那么设 $ dis[x][y][s] $ 来表示还没去过 \(s\) 集合中的点，并且当前坐标在 \((x,y)\) 的最短距离。
直接BFS更新。
又发现 $ dis[x][y][s] $ 的三维中 \(s\) 在很多点用不到，那么就会有浪费。
所以直接在P个点定义 $ dis[i][s] $，在第 \(i\) 个点时的最短路。转移的时候利用两个点的最短路即可。
关于体积问题，在每个点都会重新膨胀，那么其实在每个点的最大膨胀值是可以处理出来的，直接在BFS过程中加入答案一起统计即可。
9.3
T1
组合数，树转化为序列，那么组合就是子序列。所以对于每一个子序列，都定义其最大值为最大值里位置最靠后的。那么我们就需要枚举这个最大值，看看有多少个子序列的最大值是它，也就是转化为每个点的贡献。
那么我们就需要去满足子序列在这个位置左边的，数字不会超过这个位置上的数，在位置右侧的子序列，数字都小于这个位置上的数字（最靠后）。
若我们一共找出有 $ m $ 个这种数字，那么 $ C_m^{K-1} $ 就是这种序列的个数。
怎么找这种数字？考虑把序列按照值为第一关键字，位置为第二关键字去从小到大排序。之后就发现对于每个位置，如果它的排名是 $ p-1 $，那么数字的总数就是 \(p-1\) 。
那么扫一遍就可以统计出答案了。
T2
发现按照题目要求的话最终一定会回到起点。
那么我们考虑去从最终到达的特定位置向单一方向出发，那么设辅助数组 \(F(x,y)\) 去表示单次出行离开最终的位置 \(x\) 的时间时你距离最终位置距离为 \(y\) 的方案数。
那么有 $ F(1,1)=1,F(x,y)=F(x-1,y-1)+F(x-1,y+1) $。
那么就有递推式子，用矩阵乘法优化即可通过。
T3
对于等差数列的二进制下，会有第 \(i\) 项与第 \(2^K+i\) 项在 \(K\) 位上的数字相同。
然后原数列就会有循环节，拆出来就行。
9.5
T1
先转化一下 \(i|j==k\) ，那么答案就是前缀最大。
那么就直接去考虑每个 \(K\) 怎么求答案，发现可以直接枚举子集。
但是直接枚举显然不行，那么我们去借助高位前缀和。
造一个结构体去捆绑一下每一个 \(K\) 代表的最大值和次大值，那么初始的时候最大值为当前值，次大值为0.然后高位前缀和，但是这里的“前缀和”所代表的时所有前缀的最大值。
T2
题目要求把两个连续的1或者0去进行操作，我们发现会不可避免地去选择它是属于前面还是后面，那么我们就去把下标为偶数的位置全部取反，记我们操作之后地字符串为 \(s',t'\)。那么不难发现，我们把元字符两个相邻并且相同的位置取反之后，等价于在新的字符串上交换这两个字符。
那么也就是说转化为，交换 \(s'\) 里两个相邻的字符，至少需要多少次操作才能把一个字符串变成另一个字符串。
那么显然如果有解的话肯定是两个字符串里相同的字符出现的次数相同。那么我们去考虑怎么计算次数。
如果对于一般的序列，我们通常去计算逆序对来解决问题，但是对于这种特殊的01序列我们会有一个更简单的方法。
设我们 \(s'\) 里第 \(i\) 个 \(1\) 的下标为 \(x_i\)， \(t'\) 里第 \(i\) 个 \(1\) 下标为 \(y_i\)，那么最小的交换次数就是 $ \sum\limits_{i=1}^{c} |x_i-y_i| $。
但是还是很麻烦，我们去接着化简。有一个套路的方法 \(a_i\) 为 \(s'\) 前 \(i\) 个里 \(1\) 的出现次数, \(b_i\) 同理，那么答案就是 $ \sum\limits_{i=1}^{c} |a_i-b_i| $。
因为每次交换两个数的时候，最多只会让一个前缀和发生变化。
有了结论之后就很简单了，直接蒜就行。
记 $ pre(i,j) $ 为前 \(i\) 个数让 $ a_i-b_i=j $ 的方案数，$ suf(i,j) $ 表示对应的后缀的方案数，那么贡献就是 $ pre(i,j) \times suf(i+1,-j) \times |j| $。
T3
就是每次可以更改一个位置上的数，希望让有特定位置关系的极差变小，求最小操作数。
我们去按照前缀最小值把序列分段，发现每段时互不影响的。
那么对于每一段我们也需要去考虑最小值和最大值 \(x,y\)。如果 $ y-x==f(a) $，那么我们必须去选择一个位置 \(i\)，把它之前的 \(x\) 和它之后的 \(y\) 全部删掉，最终也就是求最小值。
直接前后缀和做就行。
9.6
T1
求出一个排列并且有形如 $ (a,b) $ 限制条件表示 $ a $ 必须在 $ b $ 之前，最大化它的子段和。
那么我们考虑枚举这个最大的子段和包含了哪些数，一个方案合法的充要条件是要满足下面的限制：
若存在 \(i->j->k\) 的路径，若选择 \(i,k\) ，则必选 \(j\)。
这等价于对每一条路径的点都可以分成“不选->选->不选”的形式。
我们把每个点都拆成 $ S->i_1->i_2->T，然后割三条边分别表示在某一段中，那么每个限制就是限制 \(a\) 的段小于等于 \(b\) 的段，直接把 $ (a_1,b_1),(a_2,b_2) $ 连上正无穷的边即可。
s
也就是先把权值为正的所有数都放在一起，但是全选的话也就代表着需要选很多负的，所以我们考虑直接把其中一些点扔走（左右），或者直接选上的负点来让左右两边的段都变大。
所以直接跑最小割，正值之和减去最小割即可。
T2
Latex太多了，不打了
原题：ARC127F
T3
这种异或的题一般都放到01Tire上，这题也不例外。
我们去直接设 $ f(u,v) $ 表示从 \(u,v\) 的子树中选一些数，使得凉凉异或不大于 \(X\) 的方案数。
那么答案就是 $ f(1,1) $
如果 X 当前位是0，那么 $ f(u,v)=f(ls_u,ls_v)+f(rs_u,rs_v)−1 $，减 \(1\) 是为了减掉出现两次的空集，如果 \(u≠v\)，也就是更高位出现了\(1\)，如果现在只在一颗子树中选相当于撤回了更高位的\(1\)，就不需要考虑这一位了，补上对应的方案。
如果 \(X\) 当前位是\(1\)，如果 \(u=v，f(u,u)=f(ls_u,rs_u)\)，如果 \(u≠v\)，发现 $f(ls_u,rs_v) $ 与 $ f(rs_u,ls_v) $ 相互独立，也就是 \(f(u,v)=f(ls_u,rs_v)×f(rs_u,ls_v)\)。
DP即可。
9.8
T1
树形DP+容斥。
我们定义 \(g_i\) 去表示 \(i\) 个点两两配对的方案数，若是奇数则为 \(0\)，偶数就是小于 \(i\) 的拘束的积。
那么我们接着设 \(f_{i,j}\) 表示 \(i\) 的子树里，包含 \(i\) 的连通块大小为 \(j\) 的方案数，并且设 $ f_{i,0} $ 为 \(i\) 的子树内全部匹配的方案数。
大概就像树形背包一样转移。
我们对于 \(f_{i,0}\) 的转移，需要加上一个 \(-1\) 的系数，原因是它上面还有一条边链向父亲，需要割掉，集合大小 \(+1\)，并且其转移为 $ f_{i,0}=-\sum\limits_{j=0}^{siz} f_{i,j}\times g_j $。
最后对于根的集合大小则不用 \(+1\)，直接输出 \(-f{1,0}\)。
T2
无解情况显然可以判定，我们考虑怎么去用最小的花费转移为回文串。
我们发现对于每种字符，他总是首尾匹配的。更具体地说，我们直接从前往后扫，如果扫到一个没有匹配上的，我们就将这种字符的最后一个同种字符与他相匹配即可。也就是说如果这个字符位置为 \(i\)，与之匹配的位置就是 \(n-i+1\)。
可以验证这种交换方式是最优的。
所以直接求逆序对就行。
T3
阴间题，大体来说就是维护两个栈，同时碰到首尾相同的字符就消掉，看能不能消完即可。因为是贺的，所以不再阐述。
9.9
T1
区间LCM，想一想LCM的性质，本质就是把两个数质因子分解，然后每个因子的次数取个最大值。
考虑根号分治，先想因子小于等于 \(\sqrt{a}\) 的情况：
发现对于值域内不会超过\(86\)个质因子，那么就是对于每个因子次数区间求最大值，直接线段树。
对于另一种情况，我们发现这么大的质因子对于每个 \(a_i\) 只可能有一个，如果有就直接单独处理即可。对于不含有此因子的数，视为 \(1\)。
那么就是询问区间内所有不同的大质数的乘积。
我们和区间统计数字种类相似的，预处理一个 \(pre\) 数组去表示每个大质数数上次出现的位置，然后询问就变成了区间里 \(pre\) 小于等于询问左端点的所有 \(a_i\) 中大质数的乘积。
那么直接用主席树维护，每个位置 \(i\) 都用一棵线段树去维护 \(1-i\) 内 \(pre\) 在一段区间内的大质数乘积即可。
最后别忘了乘上就行。
T2
神必的期望。
考虑枚举第一格的数，那么我们需要知道 \(f[i][j]\) 表示长度限制为 \(i\)，结束时第一格为 \(j\) 的概率，\(g[i][j]\) 表示此时答案的期望。
求 \(f\) 和 \(g\) 时需要知道 \(x[i][j]\) 表示长度限制为 \(i\)，第一格弄出 \(j\) 的概率，以及 \(u[i][j]\) 表示长度限制为 \(i\)，初始时第一格为 \(j\) 的期望答案。
具体转移方程可以参考标程。
写出转移方程后不难发现将 \(g[i][j]\) 改为长度限制为 \(i\)，初始时第一格为 \(j\)，结束时第一格还是 \(j\) 的概率*期望，就可以不用记 \(f[i][j]\)，同时转移方程会简化很多，
复杂度还会少个 \(log(\)模数\()\)。
时间复杂度 \(O(nm)\)。
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
const int N = 2005;
int n, m, t;
ll g[N];
ll f[N][N];
ll p[N][N];
ll q[N][N];
ll qpow(ll a, ll b);
int main()
{
cin >> n >> m >> t;
int maxn = min(t, n + m - 1);
ll invm = qpow(m, P - 2);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= maxn; j++)
{
p[i][j] = p[i][j - 1] * p[i - 1][j - 1] % P;
if (j <= m)
(p[i][j] += invm) %= P;
q[i][j] = 1;
if (j != maxn)
q[i][j] = (q[i][j] - p[i - 1][j] + P) % P;
}
for (int j = maxn; j >= 1; j--)
{
ll tmp = (q[i][j] * j % P + g[i - 1]) % P;
if (j != maxn)
tmp = (tmp - p[i - 1][j] * f[i - 1][j] % P + P) % P;
f[i][j] = tmp;
if (j != maxn)
(f[i][j] += (1 - q[i][j] + P) * f[i][j + 1] % P) %= P;
(g[i] += p[i][j] * tmp % P) %= P;
}
}
cout << g[n];
}
ll qpow(ll a, ll b)
{
ll ans = 1;
a %= P;
for (; b; b >>= 1, a = a * a % P)
if (b & 1)
ans = ans * a % P;
return ans;
}
T3
若可以变成回文串，则至多有一种字母出现了奇数次。
那么我们考虑状压，二进制一位代表一个字母，那么整个路径的疑惑和要么是0要么是 \(2^x\)。
那么我们设 $ f(x) $ 表示 \(x\) 到根节点的异或和，然后 $ f(u) xor f(v) $ 为 \(0\) 或者 \(2^k\) 时，代表 \((u,v)\) 是一条合法路径。
那么每个点先从子树继承答案，然后开桶，子树之间计算贡献。
重儿子的话就直接继承即可。
9.12
T1
把这个需要统计的东西莫反一下，变为 \(k|gcd\) 的数量。那么我们对于每个边权都只保留质因子是否存在即可，那么每个数的质因子都不会超过 \(7\) 个。对于每一个 \(k\)，把边权是 \(k\) 的倍数的边都取出来，然后用并查集统计答案。对于我们修改涉及到的边，开始并不加入并查集，然后枚举时间轴时再逐一将其加入，统计答案，再删除即可。
T2
我们定义一下 \(w\) 为前缀异或，即为 \(w_k=0 \ \oplus \ 1 \ \oplus...(k-1)\)，那么我们就可以把问题转化为寻找数对满足 \(0 \le i < A,0\le j<B,w_i\oplus w_j=V\)。
那么对于 \(w\)，有一个经典结论: $ w_{4x}=4x,w_{4x+1}=1,w_{4x+2}=4x+3,w_{4x+3}=0 $
那么发现只需要确定了 \(i,j\) 模 \(4\) 的余数所有可能的情况即可。
直接把 \(V/4\) 和 \(V\mod 4\) 分开算，分别取枚举 \(l\mod 4,r\mod 4\)。计算有多少个 \(l/4,r/4\)异或和为 \(V/4\)，寄搜就行。
T3
看到这种条件计数题，可以思考一下什么样的图形符合条件。
画一画图发现，不可能有 \(\le 3\) 个黄色的分开部分，否则就会有一行多个蓝色块。
并且不可能黄色全连通并且蓝色也全连通。
假设现在统计黄色的两个部分分开的方案数,这时候就需要多画图，找出符合条件的情况。
情况如下，这是左边黄色块在右边黄色块下面的情况。也可以在上面，只要把答案乘上 2 。
如何计算个数？
考虑枚举中间那条虚线的位置，再枚举 2 个红点的位置，计算符合条件的黄色块边界数量。
这个可以通过 4 个角到某几个点的路线方案数乘起来计算，路径方案数显然是组合数。
见下图：（由于枚举的是右上角，左下角，所以最后一步的方向是确定的。）
然后前缀和优化即可。
还要计算蓝色两块分开的方案数，直接交换 \(n,m\) 算就行了。
然后就会发现算重了，蓝色、黄色都分开的重复算了。
其实很好处理，在算蓝色的时候强制让两个红点相差 \(\ge 1\) 即可。
有一点点细节，画画图就会了。
9.13
T1
你在 \(A\) 上建棵主席树，每个点都去储存到根节点路径上的信息。
然后求出来每个点在 \(B\) 树上的DFS序，在 \(A\) 树上建主席树的时候把每个点在 \(B\) 树上的子树对应区间去进行一个最大值的覆盖的做。
然后询问就成了询问点的最大值。
T2
T3
神必的数数题。
把他放在二维的坐标系上，\(x,y\)轴分别表示它往左走和往右走的步数，每个机器人的坐标就分别表示了它需要走的步数，那么一个机器人在何时溜走就看他是先过 \(x\) 轴上的界限还是 \(y\) 轴了。
那么若一个机器人的坐标定义为 \((a_i-0.5,b_i-0.5)\)，所有在曲线左上方的都会从左侧的出口溜走，右下方的反之。
那么对于每一个从右侧出口溜走的机器人集合，就可以构造出一个唯一的与之相对应的折线。
方案数显然就是这种直线的个数。令 \(f_i\) 去表示延伸到 \(i\) 的机器人，并且这是个机器人，那么转移方程就是 $ f_i=\sum\limits_{a_j<a_i,b_j<b_i}f_{j+1} $。
那么借助树状数组去数点，优化到 \(O(nlogn)\)。
9.14
T1
区间出现概率严格大于 \(p\) 的数，由于题目给出的限制较为宽松，只要包含即可，那么我们就直接用摩尔投票在多人情况下的拓展即可解决，剩下的就是普通的线段树维护了。
摩尔投票：找区间绝对众数的方法，具体方法是一个一个去抵消，可以理解为粉丝给爱豆投票，两个粉丝发生冲突的时候会互相把对面打残了然后就不能参加投票了。
T2
CTSC题，牛的一比。
我们先直接去考虑暴力做法。发现一种方法是我们把 SAM 建出来，然后 \(O(n)\) 去枚举起点，\(O(n)\) 去 dfs ，不断拓展 v，那么就可以边 dfs 边在 SAM 上匹配字符串，最终复杂度 \(O(n^2)\)。
考虑另外一种暴力做法，我们发现每一对 \(u,v\) 都会有一个 LCA，并且可能会有很多对不同的点对 LCA 相同，那么我们考虑一个 LCA 可以对它所“管辖”的点对造成多少贡献。
我们不妨定义 $ F(x)=\sum\limits_{x\in k的子树}\sum\limits_{y\in k的子树}Occur(Path(x,k)+Path(k,y)) $ ，那么我们所
求的以 \(k\) 为根的子树的答案就是
$ F(k)-\sum\limits_{x\in k的直接孩子}F(x) $，也就是所有链对的出现次数和减去最近公共祖先不在Z的所有链对的出现次数和。
函数 \(F\) 的计算可以使用我们刚才讨论的方法。 我们建立母串S的后缀树和母串 S 的逆序串 Srev 的后缀树，然后从 \(k\) 结点出发 DFS 一遍，记录下各个结点在两棵后缀树上对应到达的位置。 然后对两棵后缀树均 DFS 一遍，把标记推下去到叶子结点（对应着匹配的后缀在串中位置，从而得到串中的每个位置开始各能匹配多少个 \(k\) 出发的串，然后把对应位置的匹配数目相乘并求和，即可求出 \(F(k)\) 的值。
那么我们发现这个朴素算法可以改进一下，算法中的 \(n^2\) 实际上是各个子树的大小之和。但是这是一棵无根树对吧，所以我们考虑淀粉质去选取树的中心作为根节点来分治，可以把复杂度优化到 $ O(NlogN+MN) $。
有了上面点分治的改进后，我们发现，时间复杂度的瓶颈已经变成了每次 DFS 后缀树
的 $ O(M) $。 而这个复杂度难以优化。我们发现，计算 \(ans(k)\) 的复杂度不管 \(k\) 的子树有多大都
始终是 $ O(M) $，这对于较小的子树显然很浪费。 而朴素算法晁的复杂度正好是与 \(M\) 无关的，始终是子树大小的平方。于是我们产生了一个想法，如果分治得到的子树足够小了，就不妨把任务交给第一种朴素算法来做，这样显然比用朴素算法划算很多。
我们不妨假设当子树大小不超过某个值 \(S\) 时我们将使用第一个朴素算法。因为我们选取重心作为根结点进行点分治，所以我们可以保证，每次分治得到的最大子树大小不会超过原子树大小的一半。复杂度可以得到保证（O（能过））。
9.16
T1
T2
T3
首先我们使用 01Trie 上二分的方式来求出“第K大”，令求出来的为 kth
当然这一步也可以直接二分 \(O(nlog^2n)\)，但是可以做到 \(O(nlogn)\)。
然后我们需要求出所有“大于第k大”的异或和的和
怎么做呢？
我们贪心地从大到小考虑 kth 的每一位，如果发现某一位为 \(0\)，那就说明有空隙
我们就得把所有异或和中 "这一位为\(1\)" 的数求个和，然后累加到答案。
这玩意我们可以预处理处 \(cnt[x][y]\) 表示 以 \(x\) 为根的子树中有多少个数有 \(y\) 这一位，然后每次要求和的时候拆位，一位一位累加，可以做到 \(O(nlog^2n)\) 的复杂度。
别忘了long long。
9.20
T1
怪题，看到数据范围我啪的一下就是一个表啊，很快啊
直接DP转移打表即可。
T2
这玩意一看就一眼不可做。。。
我们先把和转化为期望，然后最后再乘上方案数即可。
由于Latex不好打，我们这里直接放图片。
T3
显然我们移动肯定是比不动要更快的，所以直接考虑怎么移动。
那么这个操作的本质就是给原序列分为很多小组，并且认为划定一个峰点，峰点左侧向右走，右侧向左走，最后双向奔赴。
那么每个点都会由两种状态构成，要么先向左匹配之后再回头匹配，要么就是先向右匹配。
所以我们定义一下如果 $ p_i $ 行为 \(2\) 而 $ p_{i+1} $ 行为 \(1\)，那么 \(i,i+1\) 均为匹配状态。
那么有一个结论：最优解中是不存在连续两个不匹配的点的。
所以我们直接强制让 \(f_i\) 为匹配 \(i,i-1\)，dp即可。
9.22
T1
注意到了 $ |a_i -b_i|\le 12 $，可以状压连通块了。
看上去状态很多，实际上因为它图本身限制，你在跑的时候判断一下连通性的话就可以省掉很多的无用状态，
所以实际上跑的飞快。。。
然后状压就行。
T2
ARC135F
T3
如果把所有可能的最终集合排序并且找到字典序（我也不知道怎么表述了……）最大的。显然就是在第 \(i\) 次插入时插入 \(i\) 可以使得字典序最大。
那么，如果一种集合的字典序大于这个最大的字典序，那肯定无法构造。反之则必定可以构造，下面是一种方案
把所有出现在最终集合中的数从小到大插入，如果碰到操作2就插一个不在最终集合内的数垫背。
最后再写一个 \(O(n^2)\) dp，就很简单了。
9.23
T1
给定 \(1 \dots N\) 的一个排列 \(a\)，共有 \(M\) 次操作，包含两种：
1 l m r表示将区间 \([l,r]\) 内的元素修改为 \(merge(\lbrace a_l,\ a_l+1,\ \dots,a_m \rbrace, \lbrace a_{m+1},\ a_{m+2},\ \dots,\ a_r)\)。2 x表示询问 \(a_x\) 的值。其中
merge(a,b)表示归并操作，代码如下：def merge(a,b): c=[] while a.size() and b.size(): if a[0]<b[0]: c.append(a[0]) a.pop_front() else: c.append(b[0]) b.pop_front() return c+a+b\(N,\ M \leq 10^5,\ 1=l \leq m < r \leq N,\ 1 \leq i \leq N\)。
对于每一组 \(1\) 操作，我们先考虑区间 \([m+1,r]\) 内的元素最终的位置在哪。不妨设 \(f(i)\) 为区间 \([l,i]\) 的最大值，\(g(i)\) 为区间 \([m+1,i]\) 的最大值，那么右区间的一个元素 \(a_i\)，经过一轮 merge操作后的位置就是 \(k+i-m\)，其中 \(k\) 为满足 \(f(k)<g(i)\) 的最大值。
形象地说，在每一次 merge 操作结束后，区间 \([m+1,r]\) 的每一个元素最终所处的位置将区间 \([l,r]\) 划分为了若干小段，每个小段都是原区间 \([l,m]\) 的一段连续子区间。显然上文所说的 \(k\) 可以通过二分在 \(O(\log n)\) 的时间内得到，我们需要做的就是维护一个支持区间分裂合并的数据结构，这里使用 \(Fhq-treap\) 实现。
利用上述方法，发现左区间同样对右区间产生着相同的贡献，相应的维护即可。这样的时间复杂度是均摊的，不会理性证明，但是可以这样感性理解：设 \(P_i\) 为第 \(i\) 次操作后整个排列 \(a\) 的前缀最大值所构成的序列，显然 \(P_i\) 的字典序是单调不上升的，而当某一次操作导致 \(P\) 的字典序最小后，整个序列变为有序，此时进行 \(1\) 操作的时间复杂度为 \(O(1)\) ，而在这个时刻之前的修改操作所花费的时间也在随着 \(P_i\) 字典序的变小而降低，根据实际表现，最终大概会均摊至 \(O(n \log^2 n)\) 左右的复杂度。
T2
给出一个序列 \(\lbrace 1,\ 2,\dots,\ n \rbrace\)，可以对它进行 \(m\) 次以下操作：
- 删除任意一个数，将它加到这个序列的开头或者末尾。
最后你需要得到序列 \(\lbrace a_i \rbrace\)，其中 \(a_i\) 同样是 \(1-n\) 的一个排列。求合法的方案数模 \(998244353\)。
两种操作方案相同当且仅当每次操作都选择了相同的元素，移动到了相同的方向。
\(2 \leq n \leq 3000,\ 1 \leq m \leq 3000\)。
首先注意到，对于一个数，只有最后一次操作有意义。
那么对于每个数只保留最后一次操作，称其为简化操作序列，假设长度为 \(k\)。那么出去简化操作之外的其它操作的方案数就是： \(\dbinom{m}{k} \times 2^{m-k}\)。
接下来考虑简化操作序列的方案数。发现如果把序列 \(1-n\) 中的一些数抽出去，那么中间剩下的就是一段递增的数列。在 \(a\) 中枚举这个递增区间 \([l,r]\)，那么 $a_{1},\ a_{2},\dots a_{l-1} $的最后一次操作就是向左的，而 $ a_{r+1} \dots a_{n} $ 就是向右的。
那么我们已经把操作方向确定，并且向左的操作之间的顺序也已经确定，但是左右操作之间的交换顺序还是任意的，可以随便排列。
随意这部分的方案数 $ \dbinom{l-1+n-r}{l-1} $。
那么答案就是 $ \sum\limits_{k=0}{n}f(k)\dbinom{m}{k}2{m-k} $。
其中 $ f(k) $ 表示长度为 \(k\) 的合法简化操作序列数量。
T3
在一个长度为 \(n\) 的序列里面挑 \(m\) 个数使得挑出来的数在原序列里面不相邻，对每一种合法方案都求出这个序列的 \(sum\)，求所有合法方案的 \(sum\) 和对 \(998244353\) 取模。
一道F题。
我们先定义一下 $ ring(n,k) $ 在一个长度为 \(n\) 的环里面选取 \(k\) 个的方案数，而 $ line(n,k) $ 表示在一个长度为 \(n\) 数组里取 \(k\) 个的方案数。
那么我们由插板法可得 $ line(n,k)=\dbinom{n-k+1}{k} $， $ ring(n,k)=line(n-1,k)\times$ 第一个元素不取 $ +line(n-3,k-1)\times $ 第一个元素取，所以都是可以直接求的。
那么就把原题转化为一个数可以在多少个满足条件的序列里存在，乘起来再加上就是答案。
那么我们发现为环时， $ cnt_i=\frac{ring(n,k)\times k}{n} $。
为序列时，只多了 \(a_1,a_n\) 都可以取到的情况，那么就可以直接递归了。
最终复杂度 \(O(n)\)。
当然这题还有个EX，具体就是把不能选连续的 \(2\) 个原序列元素改为了不能选连续的 \(d\) 个，感兴趣的可以思考一下我不会。