随记
随记?标题那个词时百度翻译的，，，，
1. \(\mu(ix)\) 怎么筛？
可以杜教筛，很震撼。
\(f_x(i)=\mu(ix)\) 这个函数首先是积性的，不包含的质因子直积形成的，而他的的贝尔级数为：\((1-x)\) 和 \(1\)。
我们构造 \(g_x(i)=[\gcd(x,i)=1]\)。他的贝尔级数为：\(1+x+x^2+\cdots +x^n+\cdots\)，和 \(1\)。
发现很神奇呀，乘起来之后就是 \(\epsilon\)。
特别的 \(\phi(ix)\) 的杜教筛法也是类似的。
2. 感性理解对偶。
\[ \begin{aligned} \max c^{T}x,Ax\le b,x\ge 0\\ \min y^Tb,A^Ty\ge c,y\ge 0\\ \end{aligned} \]
限制与变量对调，限制系数与目标函数系数对调。
\[ \begin{aligned} y^TA\ge c^T\Rightarrow y^TAx\ge c^Tx\Rightarrow y^Tb\ge y^TAx\ge c^Tx \end{aligned} \]
这样我们得到了 \(\min y^Tb\ge \max c^{T}x\)。
接下来证明等号很复杂，所以感性理解 \(\mathrm{maximize}\) 也始终小于 \(\mathrm{minimize}\) 最终取等？
3. 复杂度真的不对吗？
我们都知道，值域是 \(sz_u\) 的树背包 dp 的复杂度是 \(O(n^2)\) 的。
那么如果值域变成了 \(\min(sz_u,k)\) 这类的，他的复杂度啥呢？
答案是通过精细实现，是 \(O(nk)\) 的。
大概是你考虑将合并分成三部分。
我们称 \((u,v),sz_u>k,sz_v\le k\) 为切换边，那么切换边下面的转移复杂度可以用 \(\sum_{v}sz_v^2\) 来分析，由于是不交的，所以有 \(\sum_{v}sz_v^2\le \sum_{v}sz_vk=O(nk)\)。
切换边上面的点总共只有 \(n/k\) 个，那么直接转移的复杂度是 \((n/k)k^2=O(nk)\) 的。
切换边的转移代价可以用 \(\sum_{v} sz_vk\) 来分析的，又是 \(v\) 不交，所以这部分也是 \(O(nk)\) 的。
这个其实给了我们一些启示，如果能将树分成若干个“不交并”的这样的集合，那么很多事情会变成 \(O(n)\) 。
例如『MdOI R1』Path 这题的 \(n\log n\) 做法，几次利用到了不交并关键性质。
『MdOI R1』Path
考虑全局最大异或和的链，实际上有很多链的答案是他们。性质太棒了。4.原汁原味的淀粉。
如题，如果需要维护点集 \(A\)，每次插入一个数，查询 \(f(u)\sum_{x\in A}dis(u,x)\)。
这个问题我最开始以为拆贡献，变成链加，链求和是最为方便的做法。可惜不用全局平衡二叉树的话，树剖是 \(\log^2\) 的。
那么如果使用点分树的话呢？，考虑点分树这样一个结构，点分树上两点一定在原树路径上。
我们之前干的事情是把路径集合，划分成若干个落在lca处的不交并。这样我们可以把路径集合落在点分树上lca处的不交并。
好处是明显的，树高 \(\log\) 一些我们平时不敢干的事情可以暴力做了。感觉做法很有拓展性。
当然我们知道 toptree 的结构更加有拓展性。记得u群里总说直接在toptree上分治。全局平衡二叉树是静态toptree。
5.英国的将军算法。
不知道这玩意咋想出来的。。
如何求 \(a\cdot m^{-1}\bmod M\)。
waiting for upd
6. 区间点积真的啥操作都能维护呀！
区间点积真的啥操作都能维护呀！
记录 \(sa,sb,sab\) 足以了。。。。。。。。。。
不用 \(5\times 5\) 矩阵。。。。。
7. MTT
\(a_i,b_i\in \mathbb{Z}\)。
\(f(x)=A(x)+iB(x),g(x)=A(x)-iB(x)\)
\[ \begin{aligned} [x^k]f(x)=\sum_{j=0}(a_j+ib_j)(w_{n}^k)^j\\ [x^{n-k}]g(x)=\sum_{j=0}(a_j-ib_j)(w_{n}^{n-k})^j\\ \end{aligned} \]
\(\overline{a_j+ib_j}=a_j-ib_j\)
\(\overline{w_{n}^k}=w_{n}^{n-k}\)
\(\overline{[x^k]f(x)}={[x^{n-k}]g(x)}\)
8. agc的c的證明。
如果一个完全图，我给每条边都定向，产生的无向图有环。
那么一定存在一个简单三元环。对于任意一个长度>=4的环，考虑其中任意两点，不管怎么连边，必然会分成一个更小的环。