模拟赛补题解
题意简述：求树上最长回文串的长度,字符集大小为1000。
大概二分+点分治。
如果光二分，那么我们其实不好判断。
如果光点分治，那么我们也不好确定回文中心的位置。
那么就结合起来。
我们点分治的时候，dfs如果到达点 \(x\) ，那么我们记录下 \(x\) 是否有可能成为经过分治中心的回文串。
就大概如果长度 \(>mid\) 那么我们把他给从确定的回文中心回文地删掉。
剩下的一定是一个 \(y\to x\) 的链，把这个哈希掉。
如果是短链，我们就查询哈希值。
#include<bits/extc++.h>
using namespace __gnu_pbds;
gp_hash_table
没什么别的技巧。
先说 T3
题意，\(S\subset \mathbb{P}\),\(f(S)\) 表示从 \(p\in S\) 的 \(\leq n\) 的倍数最多选几个，使得一个不是另一个的倍数。
显然整除是偏序关系。
longest antichain = minimum chain cover. （其实我的做法没有用到。。。
这个好像比较经典。
如果是 \([1,n]\) 中，选出，那么答案必然是 \(n-n/2\)，也就是选 \([n/2+1,n]\)。
这个是极大的，因为任意一个 \(\leq n/2\) 的数都在 \([n/2+1,n]\) 里面有倍数。（\(n/2\leq n-n/2\)）。
又是合法的，因为 \(2\times (n/2+1)>n\)。
如果非得用minimum chain cover理解，可以只考虑最后这段，这些必须是一些链的结尾。
所以这是min的上界。然后可以覆盖，然后完事了。
这样我们得到了一个和题解不尽相同的式子。 \[ \begin{aligned} &\sum_{S}\sum_{i=n/2+1}^n[p_j|i]\\ &\sum_{i=n/2+1}^n(2^{w(i)}-1)2^{all-w(i)}\\ 2^{all}(n-n/2)+2^{all}&\sum_{i=n/2+1}^n2^{-w(i)} \end{aligned} \] 发现 \(2^{w(ij)}=2^{w(i)+w(j)}=2^{w(i))}\times 2^{w(j)}\)。
面对积性函数我们现在有大概两条路。
- 杜教筛/powerful number 求贝尔级数，观察性质
- min25筛暴力筛
我尚未发现 \(2^{-w(i)}\) 的贝尔级数有什么优秀的性质，所以第一条路走不太通。
min25只需要两步。
- 不管你用什么方法，求出 \(n/i\) 这根号个位置的素数前缀和。
- 暴力组合。
尽管在 \(f(p)\) 出取值不是积性函数 \(f(p)=1/2\)，但是这个其实等价于素数个数，所以第一部解决。
第二步很显然。复杂度 \(O(n^{1-\epsilon})\)
感觉尽管做法见过，但是很难想到。
首先大意让你求 \(A=B*A\) 的矩阵对 \((A,B),|B|\not =0\)。
借着这个题记录一下矩阵乘法本质上就是对矩阵进行线性变换这个想法。 \[ M=\begin{bmatrix} 1&0&0&\cdots&0\\ 0&1&0&\cdots&0\\ 0&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1\\ \end{bmatrix} \] 左乘这个矩阵代表着不变（单位阵）。
我们在 \(M_{i,j}\) 处加上 \(v\) 代表着给第 \(i\) 行加上第 \(j\) 行。
我们把 \(M_{i,i}\) 改成 \(v\) 代表将 \(i\) 行乘上 \(v\)。 \[ \begin{matrix} 0&\cdots&1&0&\cdots&0&\cdots\\ &&\vdots&\vdots&&\vdots\\ 0&\cdots&0&0&\cdots&1&\cdots\\ \end{matrix} \] 这个其实就代表着 swap 两行。
满秩的矩阵构成群。（满秩的矩阵个个存在逆元），如果只考虑秩的话，我们不妨先消成三角阵考虑，此时因为满秩，操作矩阵也满秩，所以操作后的矩阵同样满秩。
那么问题可以转换成 \(X\) 代表全体矩阵，\(G\) 代表满秩矩阵，\(G\) 作用在 \(X\) 上，\(X\) 中的不动点。 \[ \sum_{x\in X}\sum_{g\in G}x\overline{\to} \]