一些知识点的整理

た入场券 2022-01-06 00:59 394阅读 0赞

### \\(O(n\\log n)\\)求通常幂多项式的不定和式 ###

即给定多项式\\(\\sum\_\{k=0\}^\{n-1\}a\_kx^k\\)，求\\(\\sum\_\{k=0\}^\{n-1\}a\_kS\_k(x)\\)的系数。其中\\(S\_k(x)=\\sum\_\{i=0\}^\{x-1\}i^k\\)。

考虑从奇怪的角度出发：

\\\[n^k=k!\[x^k\]e^\{nx\}\\\]

\\\[\\sum\_\{i=0\}^\{n-1\}i^k=k!\[x^k\]\\Big(\\sum\_\{i=0\}^\{n-1\}e^\{ix\}\\Big)\\\]

其中\\(\\sum\_\{i=0\}^\{n-1\}e^\{ix\}\\)可以用等比数列求和公式简化为\\(\\frac\{e^\{nx\}-1\}\{e^x-1\}\\)。发现分母和求和指标\\(i\\)是无关的，我们尝试将其分离。但是由于\\(e^x-1\\)常数项为\\(0\\)无法直接分离，所以我们考虑在等式右边乘以\\(x\\)，将\\(\\frac\{x\}\{e^x-1\}\\)分离。即：

\\\[\\sum\_\{i=0\}^\{n-1\}i^k=k!\[x^k\]\\frac\{e^\{nx\}-1\}\{e^x-1\}\\\]

\\\[\\sum\_\{i=0\}^\{n-1\}i^k=k!\[x^\{k+1\}\]\\frac\{x(e^\{nx\}-1)\}\{e^x-1\}\\\]

\\\[\\sum\_\{i=0\}^\{n-1\}i^k=k!\[x^\{k+1\}\]\\bigg(\\frac\{x\}\{e^x-1\}(e^\{nx\}-1)\\bigg)\\\]

实际上\\(\\frac\{x\}\{e^x-1\}\\)就是伯努利数的指数生成函数，我们将其简记为\\(B\\)。

那么我们直接展开两个多项式相乘的系数，可以得到：

\\\[\\sum\_\{i=0\}^\{n-1\}i^k=k!\\sum\_\{j=0\}^\{k+1\}B\_\{k+1-j\}\[x^j\](e^\{nx\}-1)\\\]

\\\[\\sum\_\{i=0\}^\{n-1\}i^k=k!\\sum\_\{j=1\}^\{k+1\}B\_\{k+1-j\}\[x^j\]e^\{nx\}\\\]

\\\[\\sum\_\{i=0\}^\{n-1\}i^k=k!\\sum\_\{j=1\}^\{k+1\}B\_\{k+1-j\}\\frac\{n^j\}\{j!\}\\\]

于是可以得到：

\\\[\\sum\_\{i=0\}^\{x-1\}i^k=k!\\sum\_\{j=1\}^\{k+1\}B\_\{k+1-j\}\\frac\{x^j\}\{j!\}\\\]

回代到原式可得：

\\\[\\sum\_\{k=0\}^\{n-1\}a\_kS\_k(x)=\\sum\_\{k=0\}^\{n-1\}a\_kk!\\Big(\\sum\_\{j=1\}^\{k+1\}B\_\{k+1-j\}\\frac\{x^j\}\{j!\}\\Big)\\\]

\\\[=\\sum\_\{j=1\}^nx^j\\frac\{1\}\{j!\}\\Big(\\sum\_\{k=j-1\}^\{n-1\}a\_kk!B\_\{k+1-j\}\\Big)\\\]

直接进行卷积即可。

板子题：[洛谷P3711][P3711]。

### 点分治中降低复杂度的一种方法 ###

有时点分治的过程要求我们求出从分治部分的根到重心的信息，如果直接做通常会成为复杂度瓶颈，使复杂度多一个\\(\\log\\)之类的。但是考虑到在递归至子树的时候我们已经做了一部分这样的问题了，我们也许可以利用这些结果来降低复杂度。设重心为\\(x\\)，考虑从重心的父亲\\(y\\)开始统计，可以发现\\(y\\)到划分给\\(y\\)的连通块的根\\(z\\)的这段路径已经统计好了，结果直接利用，但此时由于\\(z\\)被\\(y\\)递归求解了因此\\(z\\)本身并没有存下更远的路径的信息。但是\\(z\\)的父亲一定是离\\(y\\)最近的既是\\(y\\)的祖先又是点分树上\\(y\\)的祖先的点，于是它一定统计了更远的路径，并且它负责的连通块\\(size\\)至少是\\(y\\)的两倍。于是我们在目前的基础上添加\\(z\\)到\\(z\\)的父亲的信息以及\\(z\\)的父亲到所属连通块的根的信息即可。我们可以不断合并这些信息直到到达\\(x\\)的根为止。

详情可以见例题[UOJ \#23][UOJ _23]，只不过这道题是仙人掌，可能有些丑陋。其实thusc2018有一道更好的题，可以用点分治加上面的技巧在\\(O(n\\log^2n)\\)的时间内解决（不用这个方法则是\\(O(n\\log^3n)\\)的），做到了和标算一样的复杂度。有兴趣的可以上网搜一搜题目。

### 最小割的一种建图方法和个人理解 ###

最小割模型中一条\\(S\\to T\\)的路径上的边可能会被割大于一条的数量，如果想要限制这条路径最多只割一条边，可以给这条路径加上容量为\\(\\infty\\)的反向弧。

个人感觉最小割其实是在做一种类似\\(2-SAT\\)的问题，只不过最小割可以求出代价最小的一种方案（\\(2-SAT\\)的代价只能是\\(\\infty\\)），但不可以支持两个条件同时为真/假时需要付出代价的限制（但如果这类代价只会在两个不交的集合之间发生显然可以黑白染色后再用最小割做）。所以假如你感觉题目是在让你求一个有代价的\\(2-SAT\\)问题，而数据范围又不大的时候，基本可以往最小割方向想了。

### 一种吊打（？）cdq分治的离线统计法 ###

cdq分治可以用于解决一类“贡献独立，允许离线”的统计性问题。主要思想是通过对时间分治消除时间的影响，只需静态的统计前半部分的插入对后半部分询问的影响就可以了。不过，对于同样贡献独立，但是允许删除的问题，cdq分治有时就会失效。但是此时我们可以考虑更换一种分组统计的方法，建立时间线段树。此时一个插入操作对一段区间有效。对于时间线段树上的每个节点，我们静态统计包含这个区间的所有插入操作对这个区间中的询问的贡献。这样我们就可以支持删除操作，复杂度和cdq分治还是一样的。

### 图的四元环计数 ###

当然由于数量很多肯定是不能随心所欲的计数的。通常四元环的贡献是边权的乘积，就以这个为例。可以像三元环计数一样，枚举所有\\(x\\to y\\to z\\)的路径。我们在\\(z\\)中记录当前所有不同的\\(y\\)的\\(x\\to y\\to z\\)的路径的权值和，在又一次枚举到\\(z\\)的时候将贡献相乘统计进答案里就可以了。复杂度也是\\(O(m\\sqrt m)\\)的。

### 利用四毛子优化常数时间复杂度 ###

有时候我们对一个对象计算答案的时候需要递归到更小的情况，这样的复杂度可能稍微超出限制。但是考虑到递归至极小的情况（比如\\(O(\\log n)\\)的级别）的时候本质不同的情况不会很多，我们可以预处理它们以直接获得答案，减少递归次数。

通常可以令复杂度除以\\(\\log\\)。

转载于:https://www.cnblogs.com/Mr-Spade/p/10722925.html

[P3711]: https://www.luogu.org/problemnew/show/P3711
[UOJ _23]: http://uoj.ac/problem/23