$dy$讲课总结
字符串：
1.广义后缀自动机(大小为\(m\))上跑一个长度为\(n\)的串，所有匹配位置及在\(parent\)树上其祖先的数量的和为\(min(n^2,m)\),单次最劣是\(O(m)\)。
但是如果跑多个串，总长为\(n\),可以证明所有串长相等的时候复杂度更劣，设有\(k\)个串，那么复杂度为：\(O(k(n/k)^2)\)，这个时候\(k=\frac{n}{\sqrt{m}}\)最劣，是\(O(n\sqrt{m})\)
2.反串\(parent\)树就是压缩节点后缀树。
3.后缀树可以用后缀数组来利用\(dfs\)序建立。
4.\(SAM\)增量构建第三种情况就是\(endpos\)分裂和对于不同的\(len\)的分割。
5.最小表示法是一个串的循环中字典序最小的那个。
6.\(border\)不仅应用在\(kmp\)中，在后缀数据结构中也有很大的用武之地。
7.\(exkmp\)或者说\(Z-function\)算法和马拉车算法类似，都是优化暴力算法。
8.后缀自动机的\(endpos\)集合和区间一起可以直接判断子树内部的\(pos\)情况。
9.\(parent\)上\(dp\)是常见套路。
10.\(parent\)上\(dp\)是因为结构是树形，而不同于图上的结构难以\(dp\)。
11.01串要记住不是0就是1.
12.随机数据下一堆和为\(n\)的串的长度期望为\(ln n\)。
13.树上的问题转化成\(dfs\)序+离线可以用扫描线。
14.有些只能写暴力的题可以考虑用根号分治和根号重构。
15.期望题不对串作限制或者说枚举所有串的一般来说都是在枚举模式串的子串。
16.猫咪
就是一个价值的\(parent\)树\(dp\)，区别是这次从上向下\(dp\),取min和max那里细节很多。
既然要求每个串出现两次，其实可以认为其中一个就是自己的后缀，因为可以证明直接跑后缀可以涵盖所有情况。
这样的话直接查询另外一个位置存不存在就可以了。
用可持久化线段树合并来做。
数据结构：
最毒瘤没有之一。
1.倍增并查集用于区间对应连边。
2.\(splay\)题不一定用\(splay\)，\(set\)有时候也可以胜任。
3.题目模型是复杂度不优数据结构的时候多数时候有特殊性质。
4.\(LCT\)胜任大多数的点到根的操作。
5.\(LCTaccess\)的复杂度是均摊\(O(logn)\)的，所以用其他数据结构代替的时候可以牢记修改的次数是\(logn\)级别的，可以帮助算复杂度。
6.区间批量的\(LCTlink\)可以用扫描线+建虚点来实现。
7.动态点分治一般都搭配容斥
8.加边求边双+边双树链上求和，可以直接用\(LCTlinkcut\)+缩点，缩点的时候按照所连的边数进行启发式合并。
9.名字叫某个数据结构的一般都是用那个数据结构打暴力，正解可能是其他数据结构。
10.线段树维护单调栈可以用来求区间\(LIS\)或者\(LDS\)。
11.根据询问次数和修改次数来确定复杂度。
比如说\(O(n)\)次修改,\(O(n)\)次询问，那可以搞一个\(O(\sqrt{n})\)修改，\(O(\sqrt{n})\)询问的分块。
比如说\(O(n\sqrt{n})\)次修改，\(O(n)\)次询问，那可以搞一个\(O(1)\)修改,\(O(\sqrt{n})\)询问的分块。
最常见的就是根号平衡了。
12.打怪兽是一种贪心思路。
对于补血加血之类的操作常常需要进行元素排序来构建全局最优序列。
13.广义线段树也可以树剖
14.竞赛图的强连通分量一定由三元环组成。
15.kruskal重构树是二叉树，叶子节点是实点，否则为虚点，点权为链接两个连通块的边权最值，一条链上点权随深度单调。
16.离线+分治+数据结构，可以求出每个区间的答案。
分治：
1.批量处理，分治的复杂度优势在于批量处理，分割集合之后一同处理跨越两个集合的问题。
2.树上路径计数可以用点分治来维护。
3.通道这种神题就给出了很大的启发：
树形\(dp\)的本质是集合合并。
同一个点的贡献要挂在一起。
边分治套上可以直接优化复杂度。
虚树配边分治是一绝。
虚树上搞子树合并可以使用树形\(dp\)
4.整体二分把一堆二分一起处理，复杂度优势还在于批量处理。
5.线段树分治的复杂度优势在于区间最多分成\(log\ n\)个。
组合计数：
1.恒等式
\[\begin{aligned}
\sum\limits_{i=0}^{n}[2|i]\binom{n}{i}&=\sum\limits_{i=0}^{n}[2\not |i]\binom{n}{i}=2^{n-1}\\
\sum\limits_{i=0}^{m}\binom{n+i}{n}&=\binom{n+m+1}{m}\\
\sum\limits_{i=m}^{n}\binom{i}{m}&=\binom{n+1}{m+1}\\
\sum\limits_{i=0}^{k}\binom{n}{i}\binom{m}{k-i}&=\binom{n+m}{k}\\
\binom{n}{m}\binom{m}{k}&=\binom{n}{k}\binom{n-k}{m-k}\\
\end{aligned}
\]
2.自然数幂和
可以证明自然数幂和\(f_d(n)\)是一个关于\(n\)的\(d+1\)次多项式。
可以用微扰法证明，给\(RNB\)写过一次，现在记下来。
\[\begin{aligned}
f_d(n)&=\sum\limits_{i=1}^{n}i^d\\
&=\sum\limits_{i=0}^{n-1}(i+1)^d\\
&=\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{d}\binom{d}{i}i^j\\
&=\sum\limits_{j=0}^{d}\binom{d}{i}\sum\limits_{i=0}^{n-1}i^j\\
&=\sum\limits_{j=0}^{d}\binom{d}{i}f_j(n-1)\\
\end{aligned}
\]
这样是一个递归式，最终都将递归到最简单的0次形式，这个时候有递归边界：
\[f_0(n)=n
\]
是一个关于\(n\)的一次多项式，是0+1=1次的。
这就是归纳的基态。
假设自然数幂和\(f_d(n)\)是一个关于\(n\)的\(d+1\)次多项式。
根据上面那个微扰展开进行归纳。
可以发现后面的组合数部分也均为关于\(n\)的\(j+1\)次多项式。
那么最高次为\(d+1\)，也就是说\(f_d(n)\)是由一个关于\(n\)的\(d+1\)次多项式。
得证。
然后这个自然数幂和可以用拉格朗日插值直接暴力插出来。
可以用伯努利数暴力算出来。
他讲的我唯一不会的是用斯特林数来搞。
现在写一下。
用轮换斯特林数来将通常幂转化为阶乘幂。
\[n^{\underline k}=\sum\limits_{i=0}^{k}(-1)^{k-i}\begin{bmatrix}k\\i\end{bmatrix}n^i
\]
变换一下：
\[\begin{aligned}
n^k&=n^{\underline k}\sum\limits_{i=0}^{k-1}(-1)^{k-i}\begin{bmatrix}k\\i\end{bmatrix}n^i\\
f_k(n)&=k!\sum\limits_{i=1}^{n}\binom{i}{k}-\sum\limits_{i=0}^{k-1}(-1)^{k-i}\begin{bmatrix}k\\i\end{bmatrix}f_i(n)\\
&=k!\binom{n+1}{k+1}-\sum\limits_{i=0}^{k-1}(-1)^{k-i}\begin{bmatrix}k\\i\end{bmatrix}f_i(n)\\
\end{aligned}
\]
3.限制段长的插板可以转化为二项式反演插板容斥。
4.三位偏序问题可以用容斥原理，并交转化一下即可。
5.可以化式子然后根据组合意义来枚举序列等便于求的东西，
期望线性，概率相同的部分只需要求一个的期望然后乘方案即可。
6.高次情况可以由一次的序列转化为矩阵来求。
会用到划分斯特林。
7.模数小的时候必须要利用循环节和是否存在整除（为0）的情况。
8.很多模数比较小的时候，可以把\(i\)拆成：\(i=ap+b\)的形式继续代入化简，这样有利于减小复杂度。
9.序列配对问题可以转化为图论问题。
计数的时候用\(dp\),而且大多数时候可以用多项式卷积+\(ln,exp\)快速幂来优化复杂度。
经常配合斯特林数辅助计数。
10.常常把极值转化为至多形式或者至少形式进行容斥。
11.树上期望几乎都是两个部分分，看似成环的高斯消元和本质上由于简单的\(dp\)结构所以可以系数递推。
12.\(Dilworth\):最长链等于最小反链覆盖。
13.裸的组合数式子经常用恒等式转化。
14.卡好枚举上下界可以大幅度优化复杂度。
数论：
1.\(powerful\ number\)可以用于优化数论函数筛法。
我们定义一个数\(n\)为\(powerfun\ number\)。
设其质因数分解为：\(n=\_*p^c\)
其中:\(\forall c_i,c_i>=2\)
这个东西有多少个呢？
我们可以发现所有的\(pwfnum\)均可以表示为：\(a^2b^3\)的形式。
那么我们可以这样来计算其数量。
枚举\(a\)的大小得到：
\[\sum\limits_{i=1}^{\sqrt{n}}\sqrt[3]{n/i^2}
\]
这样其实不用细算。
直接积分就可以了。
\[\begin{aligned}
ans&=\int_0^{\sqrt{n}}\sqrt[3]{\frac{n}{x^2}}dx\\
&=n^{\frac{1}{3}}\int_0^{\sqrt{n}}\sqrt[3]{\frac{n}{x^2}}dx\\
&=n^{\frac{1}{3}}(n^{\frac{1}{2}})^{\frac{1}{3}}\\
&=n^{\frac{1}{3}+\frac{1}{6}}\\
&=n^{\frac{1}{2}}\\
\end{aligned}
\]
是\(\sqrt{n}\)级别的！
2.Min25笔记：
https://www.cnblogs.com/Lrefrain/p/12318781.html
有几个是\(Min\_25\)的应用题。
3.一类模型转化
求序列\(\{x\}\)，满足：\(x_1=2,x_i<x_{i+1},x_i^j<(x_j+1)^i\)
转化第三个条件。
\[\sqrt[i]{x_i}<\sqrt[j]{x_j+1}
\]
也就是 ：
\[\forall i,\max\limits_{j=1}^{i}\{\sqrt[j]{x_j}\}<\min\limits_{j=i+1}^{n}\{\sqrt[j]{x_j+1}\}
\]
这种限制条件以及首项为2使得：
\[\forall i,x_i\in[2^i,3^i)
\]
设\(f(n)\)为在\(i=n\)是比\(i<n\)是新增了多少种\(x_i\)的方案。
然后考虑去重，直接考虑当前的\(x_i\)可以开几次根号。
那么必须要保证新开的这个根号\(d\)满足\(d|n\)。
\[f(n)=3^n-2^n-\sum\limits_{d|n,d\not =n}f(d)
\]
设\(F(n)=\sum\limits_{i=1}^{n}f(i)\)
那么有：
\[\begin{aligned}
F(n)&=\sum\limits_{i=1}^{n}(3^i-2^i)-\sum\limits_{i=1}^{n}\sum\limits_{d|i,d\not =1}f(\frac{i}{d})\\
&=\sum\limits_{i=2}^{n}(3^i-2^i)-\sum\limits_{d=2}^{n}\sum\limits_{j=1}^{\frac{n}{d}}f(j)\\
&=\sum\limits_{i=2}^{n}(3^i-2^i)-\sum\limits_{d=2}^{n}F(\frac{n}{d})\\
\end{aligned}
\]
答案就是\(F(n)\)。
然后数论部分有用的大概就这么多吧。
生成函数
还没讲完。
写一下听着比较厉害的。
1.有标号无根仙人掌计数
一个仙人掌分为根所在的环和这个环所连接的其余部分（仍然是仙人掌）。
我们把根去掉之后出现若干个挂着仙人掌的环，断开之后环成为了若干个挂着仙人掌的链，然后链翻转同构。
定义：
\(a_n\)是\(n\)个点的有根仙人掌。
\(b_n\)是\(n\)个点的有根仙人掌序列。
\(c_n\)是链长度为奇数的回文仙人掌序列。
\(d_n\)是考虑翻转之后的有根仙人掌序列。
列几个公式。
考虑\(b_n\),中序列的长度，是1或者不是1。
那么:
\[b_n=a_n+\sum\limits_{i=1}^{n}a_ib_{n-i}
\]
同样考虑\(c_n\)中序列的长度为奇数，并且是回文序列，那么：
\[c_n=a_n+\sum\limits_{i=1}^{\lfloor\frac{n}{2}\rfloor}a_ic_{n-2i}
\]
考虑\(d_n\)中如何去重，首先在所有方案中除以2来去重，然而会把回文少算半次，考虑奇偶回文补齐贡献，那么：
\[d_n=\frac{b_n+c_n+b_{\frac{n}{2}}}{2}
\]
那么\(a_n\)是由大小和为\(n-1\)多个链构成的。
设\(a_n\)的\(ogf\)为\(A(x)\)
那么，我们枚举一下一种合法的仙人掌序列。
得到：
\[\begin{aligned}
A(x)&=x\prod\limits_{i=1}^{+\infty}\prod\limits_{j=1}^{d_i}\sum\limits_{k=0}^{+\infty}x^{ik}\\
&=x\prod\limits_{i=1}^{+\infty}\left(\sum\limits_{j=0}^{+\infty}x^{ij}\right)^{d_i}\\
\sum\limits_{i=0}^{+\infty}x^i&=\frac{1}{1-x^i}\\
A(x)&=x\prod\limits_{i=0}^{+\infty}\left(\frac{1}{1-x^i}\right)^{d_i}\\
&=xexp(\sum\limits_{i=0}^{+\infty}d_iln(\frac{1}{1-x^i}))\\
ln(\frac{1}{1-x^i})&=\sum\limits_{j=1}^{+\infty}\frac{x^{ij}}{j}\\
A(x)&=xexp(\sum\limits_{i=0}^{+\infty}\sum\limits_{j=1}^{+\infty}\frac{x^{ij}}{j})\\
\end{aligned}
\]
这样我们直接\(O(nln\ n)\)预处理一下然后\(exp\)一下就得到\(A(x)\)了。
我们要的答案就是：\([x^n]A(x)\)。
\(dp\)
这个东西不是\(tricks\)了。
写几个比较厉害的题。
1.求\(n\)个点至少含有一个长度为\(K\)的环的竞赛图的个数。
首先如果一个竞赛图的大小为\(m\)强连通分量中存在的最小环长度为\(i\),那么这个强连通中存在的环的长度\(L\in[i,m]\)。
这个是显然的。
因为是个竞赛图随便画一下就可以得到这个东西了。
设\(n\)个点的竞赛强连通图的个数为\(f_n\),\(n\)个点的竞赛图个数为\(g_n\)。
根据拓扑序枚举拓扑序最小的强连通的大小容斥出答案。
设\(\{f_i\},\{g_i\}\)的指数型生成函数分别是:\(F(x),G(x)\)。
\[g_n=2^{\binom{n}{i}}
\]
\[\begin{aligned}
f_n&=g_n-\sum\limits_{i=1}^{n}f_ig_{n-i}\binom{n}{i}\\
f_n&=g_n-n!\sum\limits_{i=1}^{n}\frac{f_i}{i!}\frac{g_{n-i}}{(n-i)!}\\
\frac{f_n}{n!}&=\frac{2g_n}{n!}-\sum\limits_{i=0}^{n}\frac{f_i}{i!}\frac{g_{n-i}}{(n-i)!}\\
\end{aligned}\]
这样子用生成函数来表示就是:
\[F(x)=2G(x)-F(x)*G(x)\rightarrow F(x)=\frac{2G(x)}{G(x)+1}
\]
这样就可以直接多项式求逆搞一下了。
求得答案其实是所有\(SCC\)都小于\(K\)的方案数。
设有\(h_n\)为有\(n\)个点的每个\(SCC\)的大小都小于\(K\)的方案。
那么:
\[h_n=\sum\limits_{i=1}^{K-1}h_{n-i}f_i\binom{n}{i}
\]
事实上可以把所有的\(i\geq K\)的\(f_i\)都变成0.
那么方程简化一下：
\[\begin{aligned}
h_n&=\sum\limits_{i=1}^{n}h_{n-i}f_i\binom{n}{i}\\
\frac{h_n}{n!}&=\sum\limits_{i=0}^{n}\frac{f_i}{i!}\frac{h_{n-i}}{(n-i)!}\\
\end{aligned}
\]
可以直接分治\(FFT\)。
或者如果是线代大佬可以直接玩线性递推。
这样就解决了。
2.对于一个序列\(\{a_i\}\),每次随机选择一个数字减一，使得答案加上\(\frac{\prod\limits_{j=1}^{n}a_j}{a_i}\)。
求\(K\)轮后答案的期望。
很妙的转化题意和\(dp\)转移分析，转移分析很像省选26的T1。
考虑序列乘积：
\[\frac{\prod\limits_{j=1}^{n}a_j}{a_i}(a_i-1)=\prod\limits_{j=1}^{n}a_j-\frac{\prod\limits_{j=1}^{n}a_j}{a_i}
\]
发现最开始序列的乘积-当前序列的乘积就是答案。
所以我们只需要求得\(K\)轮后序列乘积的期望即可。
很妙的转化。
设\(dp_{S,i}\)为集合\(S\)中的元素经过\(i\)轮后这个集合中所有元素乘积的期望。
设全集为\(R\)。
那么答案就是:\(dp_{R,K}\)
考虑转移。
两种情况：
\[dp_{S,i}=dp_{S,i-1}-\frac{1}{n}\sum\limits_{j\in S}dp_{S-\{j\},i-1}
\]
然后现在考虑一下有多少个\(dp_{S,0}\)转移到了\(dp_{R,K}\)
考虑大小为\(k\)的集合，那么做第二项转移的次数就是\(n-k\)。
考虑贡献：
对于每一种大小为\(k\)的集合，贡献是\(dp_{S,0}(-\frac{1}{n})^{n-k}\)
考虑其实是在\(K\)次操作中加入了有编号的\(n-k\)个元素。
那么方案就是:\(K^{\underline{n-k}}\)。
设\(f_i=\sum\limits_{S\subseteq R}dp_{S,0}[|S|=i]\)
也就是说：
\[E=\sum\limits_{i=1}^{n}f_i(-\frac{1}{n})^{n-i}K^{\underline{n-K}}
\]
然后是一个熟悉的多项式:
\[f_m=\sum\limits_{|S|=m}\prod\limits_{x\in S}a_x
\]
然后用多项式统计一下：
\[\prod\limits_{i=1}^{n}(a_ix+1)
\]
这个直接分治\(FFT\)一下就可以了。
那么：
\(f_m=[x^m]\prod\limits_{i=1}^{n}(a_ix+1)\)。
复杂度是\(O(nlog^2n)\)的。
3.三个人吃寿司，共有\(n\)个寿司，每个人对这\(n\)个寿司都有一个喜好排列。
越靠前越喜欢，每次三人分别选出当前最喜欢的一个吃掉，当某一轮某个寿司被两个人选了。
那么直接\(GG\),前两个人\(A,B\)的排列已经出现了。
求第三个人\(C\)有多少个排列使得最终不会打架。
两个要素。
吃寿司的序列和序列如何对应到\(\{C\}\)上。
先考虑后者。
吃寿司的顺序是\(A_i\),\(B_i\),\(C_i\)。
在排列\(C\)中。
\(A_k,B_k\)必须都要在\(C_k\)之后，否则就打起来了。
这样每个位置要选的方案是一定的。
那么乘起来就是要的答案:
这里\(dy\)写错了。
应该是：
\[\prod\limits_{i=0}^{k-1}(3i-1)(3i-2)
\]
然后考虑前者。
假设当前要确定\(C_t\)。
设某个序列中的某个值的位置为\(p(A_t)\)
这个东西不能为\(\forall i\in[t,k],C_t\not=A_i,B_i,C_i\)。
同时：\(forall i\in[1,p(A_t)],C_t\not =A_i\)。
\(forall i\in[1,p(B_t)],C_t\not =B_i\)。
这样去掉选择的个数就是:
\[n-3(k-t)-|\{A_1…A_{P{A_t}}\}\bigcup\{B_1…B_{P(B_t)}\}|
\]
\[3t-w_{P(A_t),P(B_t)}
\]
设\(dp_{t,x,y}\)为\(t\)轮中\(A\)的前\(x\)个和\(B\)中的前\(y\)个已经被吃了的方案。
分别对\(x,y\)转移即可。
这里\(dy\)没写怎么转移。
我自己\(yy\)一下子。
\(dp_{t,x,y}=dp_{t-1,x-2,y-2}+dp_{t-1,x-2,y-1}+dp_{t-1,x-1,y-2}\)
也就是是否吃掉了对方的某个需要的寿司。
复杂度是\(O(n^3)\)的。
4.有\(n\)家餐厅位于数轴上的\(1,n\)的位置，初始时你位于0，如果吃了\(a\)的食物，那么移动一步的代价是\(a+1\)。如果经过了第\(i\)个餐厅并且没有吃过，可以进去吃\(a_i\)克食物，求总代价不超过\(m\),走回原点的情况下做多可以吃多少克食物。
考虑一定是先过去回来的时候吃比较划算。
设：
\(dp_{i,j}\)为前\(i\)家吃\(j\)克的最小花费。
设当前答案是\(ans\)。
也就是说\(dp_{i,(ans,+\infty]}>m\)
然后考虑转移：
\[dp_{i-1,j}\rightarrow dp_{i,j'}
\]
如果能够转移的话满足以下条件。
\[dp_{i,j'}\geq dp_{i-1,j}+i(j'-j+1),j'>ans
\]
如果\(i(j'-j+1)>m\)必然不可行。
也就是说：
\(i(ans-j)\leq m\)
这样需要转移的\(j\)的个数是:\(ans-j\leq \frac{m}{i}\)
所以能转移过去的个数只有\(O(\frac{m}{i})\)个。
这样复杂度就是调和级数了。
\(O(nln\ n)\)
5.用一堆正方形覆盖一条长度为\(n\)的线段，保证覆盖的起点和重点都为整点，有\(m\)个关键点。
正方形边界不能在关键点上，也不能越过\(0\)和\(n\)的位置。
求所有情况下正方形的面积的乘积的和。
可以发现正方形面积的乘积是这样的。
假设我们的正方形将数轴分为\(p\)个段。
段长分别是\(\{len_i\}\)。这种情况对答案的贡献就是：\(\prod\limits_{i=1}^{p}len_i^2\)
相当于是分成了的\(p\)个段中任选出两个点的方案。
我们可以设\(dp[i][0/1/2]\)表示前\(i\)个点，第\(i\)个点所在的段中已经选了\(0/1/2\)个点的方案。
因为\(n\leq 10^9\)所以直接矩阵乘优化就行了。
6.对于一个排列\(\{a_i\}\)来说。
对于每一个\(i\)，定义\(l_i\)为满足\(x
求出\(\sum\limits_{i=1}^{n}min\{i-l_i,r_i-i\}=K\)的排列个数对指定质数取模的结果。
首先搞一个区间和并的原始\(dp\)。
设\(dp[i][j]\)为长度为\(i\)的排列中，\(\sum\limits_{i=1}^{n}min\{i-l_i,r_i-i\}=j\)的方案数。
那么枚举最大值所在的位置可以得到转移方程:
\[dp[i][j]=\sum\limits_{k=0}^{i-1}\sum\limits_{l=0}^{j}dp[k][l]dp[i-k-1][j-l-min(i-k+1,k)]\binom{i-1}{k}
\]
首先，因为之前左右部分的最大最小值都已经确定是正确的了(即使是被确定为\(n+1\)或者是0也是正确的，因为当前这个最大值的位置\(k\)对于之前的排列来说就是\(0\)或者是\(n+1\)），所以此时没有统计的情况仅仅是当前的最大值。
然后最大值的贡献自然是\(min(i-k+1,k)\)，可以计算的。
然而左右两个排列并没有确定相对大小关系。
所以乘上组合数\(\binom{i-1}{k}\)。
转移复杂度总共是\(O(n^6)\)的。
但是注意到其实并没有这么高。
第二维的最大值是:
\[\sum\limits_{i=1}^{n}min(i-l_i,r_i-i)
\]
而根据转移来看，其实就是一个二叉树合并，然而对于当前二叉树的根节点来说，他对上面那个公式的贡献就是他的左右子树大小较小的那一个。
那肯定是左右尽量的相等才能保证复杂度最劣。
设这个式子的最大值关于点数的生成函数为\(F(x)=\{f_i\}\)。
这样每个点最多被计算\(log n\)次，上面那个式子最大就是\(f_n=nlog n\)的。
这样复杂度就是\(O(n^4log^2n)\)的。
然后这个式子可以明显的用卷积优化。
复杂度就是:\(O(n^3log^3n)\)了。
明显还是过不去。我们把转移写成生成函数的形式。
设\(G_i(x)\)为\(dp[i][j]\)的生成函数。
那么:
\[G_i(x)=\sum\limits_{j=0}^{i-1}G_{j}(x)G_{i-j-1}(x)\binom{i-1}{j}
\]
这样的话\(G_i(x)\)其实是一个关于\(n\)的\([x^i]F(x)+1\)次多项式。
考虑暴力插值。
我们在一开始算出每一个\(G_i(x)\)的点值表达式。
那么上面那个式子就可以暴力的做了
复杂度是\(O(n^3logn)\)的。
然后询问的话直接用拉格朗日插值插出来多项式就可以了。
拉格朗日插值是\(O(n^2)\)的。
7.树上选出不相交的\(m\)条链，求经过的点权的和是多少。
因为点权不一定都是正数。
所以我们套一个\(WQS\)二分，然后变一下点权，知道求出的最优值的链子个数恰好为\(m\)。
设\(dp[x][i]\)为从当前点延伸下去长度\(\geq i\)的链以及其子树内部选择了的链个数，以及点权和的最大值。
是一个\(pair\)类型。
用没学过的长剖合并。
8.求一个长度为\(n\)的，所有数字均为\([l,r]\)组成的，\(xor\)和等于\(K\)的序列个数。
首先如果\(l=0\)，那么可以直接用交互在归的鹅妈妈那道题的思路枚举哪一位开始解放进行\(dp\)，留一个数调和结果即可。
转移可以用矩阵优化。
过程中考虑\(\geq l\)的限制就可以了。
9.定义排列\(\{p_i\}\)的代价为:\(\sum\limits_{i=1}^{n}|i-p_i|\)。给出\(n\)。求所有代价为\(K\)的排列个数。
\(|i-p_i|\)其实就是抽象出的边跨过的点的个数。
设\(dp[i][j][k]\)当前考虑了前\(i\)个位置\(j\)个位置的出边未定，计算过的权值为\(k\)的方案数。
也就是有\(i-j\)条边是内部边。
考虑转移:
可以转移到\(j-1\)或者\(j+1\)或者\(j\),\(k\rightarrow k+j\)，同时统计一下权值即可。
复杂度是\(O(n^4)\)的。
图论
1.小凸玩矩阵
二分答案
然后建二分图跑匹配。
看看最大匹配是不是大于K就可以了。
2.HUD 6403
同联赛模拟：哪天她能重回我身边
转化为图论问题，然后根据连通块是树还是基环树来进行判断和\(dp\)。
3.寿司餐厅
原题。
建图写在网络流专题里面了。
4.清华集训2014 矩阵变换
https://www.cnblogs.com/Lrefrain/p/12373898.html
5.绝地反击
我们二分答案然后可以求出一段区间。
转转转转到不能转为止必然是一种可行方案。
只需要\(O(2n)\)枚举某个点到某个端点就可以了。
这样直接上网络流，端点和弧度匹配一下看看有没有完美匹配就可以验证了。
然后因为是二分图单位流量所以复杂度是\(O(n^3\sqrt{n}logn)\)的复杂度。
可以发现转一次偏转角度是不超过两点之间的间距的。
也就是说转一下多匹配的不超过一个，不能匹配的不超过一个。
改变流量的边的个数是线性的。
加边直接加，删边减流量就可以了。
复杂度是\(O(n^2\sqrt{n}logn)\)
6.AtCoder Regular Contest 097 F
我们发现所有的黑色叶子均不会被到达。
去掉所有黑色的叶子。
那现在所有的叶子都是白色的，所以每一条边必须经过了。
然后精髓在于这个地方。
我们的操作可以进行转化:
对于经过某一条边三次的操作:
\[(u,v) \rightarrow fr \rightarrow (v,u) \rightarrow se \rightarrow (u,v)
\]
等价于：
\[flip\ u \rightarrow fr \rightarrow (u,v) \rightarrow se flip\ v
\]
是等价的。
也就是说每一条边最多走两次，最少走一次。
然后根据点的度数可以算出来需要走的代价，转化为了类似求直径的\(dp\)问题。
7.对于\(G=(V,E)\)，求每个点有多少条从他出发的长度为4的不自交的链。
\(dp_{i,j}\) 是从\(i\)走\(j\)步的方案,从某点开始的经过的三，四元环个数分别是\(th_i,fo_i\)。
那么:
\[dp_{i,2}=\sum\limits_{(i,t)\in E}deg_t-1
\]
\[dp_{i,3}=\sum\limits_{(i,t)\in E}dp_{t,2}-2th_i-deg_i(deg_i-1)
\]
\[dp_{i,4}=\sum\limits_{(i,t)\in E}dp_{t,3}-2fo_i-thi_i(deg_i-2)-dp_{i,2}(deg_i-1)+2th_i
\]
问题在于如何求三、四元环个数。
三元环：
所有边度数小的向大的连边，我们得到一个\(DAG\)。
然后枚举\((u,v),(v,w)\)查看是否存在\((u,w)\)即可。
然后考虑每一个\(w\)被算的次数。
有\(deg_u\leq deg_v\leq deg_w\)
我们发现，\(val=deg_w\max\limits_{(v,w)}deg_v\leq deg_w^2\)
然而这个环个数必然是\(val=min(deg_w^2,m)=deg_w\sqrt{m}\)
所以总共的复杂度是\(m\sqrt{m}\)
8.线性代数
写在网络流专题里面了。
9.HDU 6431
首先缩个边双树。
如果不在一个边双里面，那么就割一条就可以。
现在考虑割两条的情况。
首先做出\(dfs\)树。
考虑三种情况。
1.两个非树边（x根本割不掉）
2.两个树边
3.一个树边一个非树边：某个非树边覆盖了某条树边，而且仅被一条非树边覆盖。
第二种情况重点考虑
如果割两条树边的话。
那么必然是两条树边被某些非树边的覆盖情况是一样的。
那么对于每一个非树边\(rand\)出一个\(10^{18}\)的权值然后对其能覆盖的树边均\(xor\)上这个权值。
然后查\(Hash\)就可以知道覆盖情况是否相同了。
复杂度就是线性的。
10.TopCoder SRM 726 Div.1 Hard
可以直接跑最大费用最大流。
复杂度不对。
二分图。
尝试贪心模拟匈牙利。
用\(set\)来维护没有经过的右部点，找到一个可以经过的权值最大的点。
这样优化了枚举出边。
然后如果一个点不能增广，他以后仍然不能增广，所以可以不清空\(vis\)数组。
11.HNOI2016 矿区
看见平面图先转对偶图。
对于每一个询问
找到出现在多边形中的对偶图里面的边
非树边忽略。树边的话如果这条边所在的这面是儿子，加上子树面积，否则减去子树面积。
面积取割绝对值就行了。
12.AtCoder Grand Contest 031 Problem E
这个可以把问题转化为某一个位置的珠宝可以选择的范围。
然后一维的情况就可以直接费用流做了。
二维的情况就建两层节点串联起来。
13.WC2016挑战NPC
手机扫一扫
移动阅读更方便
你可能感兴趣的文章