Day 1
kitty
核心思路：将转移过程中的方案加入转移矩阵，边转移边累加
string
dp设计：\(f[i][x][y]\) 表示长度为 \(i\)，第一段以 \(x\) 结尾，且 \(x\leqslant p\)，第二段以 \(p\) 开头，以 \(y\) 结尾的两段完全相同的序列的对数。
对于每个 \(p\) 答案就是 \(\sum_{i=1}^{n}i\cdot f[i][x][y]\times 2^{max(0,p-x-1)}\)。
加个前缀和优化可以做到 \(O(n^4)\)。
优化：\(i\) 这维在转移的时候并没有用到，可以考虑将这维优化掉。设 \(g[x][y]\) 表示第一段以 \(x\) 结尾，且 \(x\leqslant p\)，第二段以 \(p\) 开头，以 \(y\) 结尾的两段完全相同的序列的长度和。
那么当 \(s_x=s_y\) 时，就有转移：
\[f[x][y]=\sum_{i<x}\sum_{j<y}f[i][j] \]\[g[x][y]=\sum_{i<x}\sum_{j<y}g[i][j]+f[i][j] \]容易进行 二维前缀和优化，时间复杂度为 \(O(n^3)\)
contact
类似 \(Kruskal\)
Day 2
decimal
注意到除法的借位类似于取模后 \(\times 10\)。
所以这道题可以考虑通过 \(\times 10\) 取模快速到达小数点后第 \(L\) 位，然后暴力求即可。
labor
二分区间长度，然后求区间内逆序对个数即可。
具体的，对于长度为 \(len\) 的区间，先删去 \(i-len\) 的贡献，然后再加入 \(i\) 的贡献。
这个过程用树状数组维护即可。
distance
考虑当节点存在一个 子树大小 \(>n/2\) 时，那么它必定不是优秀的。因为可以通过移动这个点，使 \(\sum_{1\leqslant v\leqslant n,v\not=u}dis(u,v)\) 更小。
综上得到第一个性质：这个点必须是重心。
对于一个点 \(u\)，要使它成为重心，需要让它的每个子树的大小都 \(\leqslant n/2\)。
到这里就可以直接考虑暴力的 换根dp，不过还可以继续对题目进行挖掘。
发现只有 \(rt\)（重心） 对应的 \(u\) 的子树个数是 \(>n/2\) 的，直接分类讨论即可。
worship
简述一下题意：求 \(1\sim n\) 所有排列产生的贡献的和，每个排列的贡献是 \(\prod_{i=1}^{n-1}dep[lca(p_i,p_{i+1})]\)。
观察式子发现，产生的贡献实质上是连续段合并产生的，也就是说可以直接考虑连续段dp。
对于 \(u,v,w\) 三个点，\(u\) 为 \(v,w\) 的祖先，\(v,w\)分别在 \(u\) 的两个子树里，产生贡献的情况只有：
\[\_\_uv\_\_w \]\[\_\_u\_\_vw \]\[\_\_uvw\_\_ \]这三种情况。设状态为 \(f[u][i]\)，表示 \(u\) 的子树中，有 \(i\) 个连续段的答案，\(g[k][i][j]\) 表示将 \(i,j\) 个连续段合成 \(k\) 个连续段的方案数。
\[f[u][k]=f[v][i]\cdot f[w][j]\cdot g[k][i][j]\cdot dep[u]^{i+j-k} \] 标签：11,结尾,cdot,题解,sum,dp,贡献,赛前,leqslant From： https://www.cnblogs.com/ATOM-/p/17836555.html