概率 / 期望 DP
有一些概率 / 期望 DP 可以快速地推出这样的式子:
- \[\begin{align} f_i&=a+bf_i\(1-b)f_i&=a\f_i&=\frac{a}{1-b} \end{align} \]
- BZOJ4872
- XSY2472
分治
有一些问题求得是只包含 / 不包含一个点的情况, 只需要考虑当前 \([l,r]\) 对 \([l,mid]\) 和 \([mid+1,r]\) 的影响
下面来讲一道例题
\(A(x)\) 为 \(n-1\) 次多项式,\(B_i(x)\) 为一次多项式,\(\forall i\) 求 \(A(x)\mod B_i(x)\)
直接做是 \(O(n^2)\) 的
因为 \((A(x)\mod C(x))\mod B_i(x)=A(x)\mod B_i(x)\)(\(C(x)\mod B_i(x)=0\))
设当前已经求出了
\[ D_{l,r}=A(x)\mod(\prod_{i=l}^rB_i(x)) \]
那么
\[ \begin{align} D_{l,mid}&=D_{l,r}\mod(\prod_{i=l}^{mid}B_i(x))\D_{mid+1,r}&=D_{l,r}\mod(\prod_{i=mid+1}^{r}B_i(x)) \end{align} \]
所以我们可以递归下去做, 直到求出所有的 \(D_{i,i}\)
时间复杂度:
\[ T(n)=2T(\frac{n}{2})+O(nlogn)=O(n{log}^2n) \]
多点求值
XSY2469
欧拉 phi 函数
就是 \(\phi\) 函数
谁都知道这个东西是个积性函数
\[ \phi(ab)=\phi(a)\phi(b)~~~((a,b)=1) \]
那如果 \((a,b)\neq 1\) 呢?
设 \(d=(a,b)\)
\[ \begin{align} \phi(a)&=a(1-\frac{1}{p1_1})(1-\frac{1}{p1_2})\cdots(1-\frac{1}{p1_{n1}})\\phi(b)&=b(1-\frac{1}{p2_1})(1-\frac{1}{p2_2})\cdots(1-\frac{1}{p2_{n2}})\\phi(ab)&=ab(1-\frac{1}{p3_1})(1-\frac{1}{p3_2})\cdots(1-\frac{1}{p3_{n3}})\\phi(d)&=d(1-\frac{1}{p4_1})(1-\frac{1}{p4_2})\cdots(1-\frac{1}{p4_{n4}}) \end{align} \]
可以发现, 对于后面那部分
\[ \begin{align} (1-\frac{1}{p1_1})(1-\frac{1}{p1_2})\cdots(1-\frac{1}{p1_{n1}})\times (1-\frac{1}{p2_1})(1-\frac{1}{p2_2})\cdots(1-\frac{1}{p2_{n2}})\=(1-\frac{1}{p3_1})(1-\frac{1}{p3_2})\cdots(1-\frac{1}{p3_{n3}})\times (1-\frac{1}{p4_1})(1-\frac{1}{p4_2})\cdots(1-\frac{1}{p4_{n4}}) \end{align} \]
如果 \(p\) 只在 \(a\) 或 \(b\) 中出现过, 那么只会在 \(ab\) 中出现如果同时在 \(a\) 和 \(b\) 中出现过, 那么会同时在 \(ab\) 和 \(d\) 中出现
所以有
\[ \phi(ab)=\frac{\phi(a)\phi(b)d}{\phi(d)}~~~(d=(a,b)) \]
逆向思维
情况一
有时候我们做某个操作很不好做, 我们可以先把所有操作做完后在一个个回复
例如: 给以一个图, 有两种操作: 1. 删边; 2. 询问连通性
我们可以先把需要删的边删掉, 再一个个加回来, 用并查集维护连通性
情况二
有时候问你 \(\forall A\), 满足要求的 \(B\) 的和
我们可以枚举所有的 \(B\), 计算每个 \(B\) 对每个 \(A\) 的贡献
AGC005F
一类全序问题
有 \(n\) 个物品, 你要依次选择这些物品, 每个物品有三个属性 \(a_i,b_i,c_i\), 当你选择一个物品后, 设当前选择的物品的 \(c\) 属性的和为 \(s\), 那么选择这个物品的收益是 \(a_i+b_is\), 问你最大收益是多少
假设我们已经钦定了一个顺序考虑两个相邻的物品 (不妨设为前两个), 什么时候当前顺序比交换后更优:
\[ \begin{align} a_1+a_2+b_2c_1&>a_2+a_1+b_1c_2\b_2c_1&>b_1c_2\\frac{c_1}{b_1}&>\frac{c_2}{b_2} \end{align} \]
这样我们就得到了一个全序关系
那么能不能扩展到任意两个物品的情况呢?
\[ \begin{align} a_i+b_ix+a_j+b_j(x+y+c_i)&>a_j+b_jx+a_i+b_i(x+y+c_j)\b_jy+b_jc_i&>b_iy+b_ic_j\\frac{c_i+y}{b_i}&>\frac{c_j+y}{b_j}\\end{align} \]
好像并不太行我们需要换一种思路
假设我们找到了一种最优解, 但并不满足以上的性质, 那么一定可以交换相邻两个物品使得答案最优所以直接排序贪心可以得到最优解
如果题目还有其他限制, 你也可以在得到这个顺序后 DP 或者干其他事情
莫队
总所周知, 莫队的时间复杂度和块大小有关
如果块大小为 \(t\), 时间复杂度为 \(O(\frac{n^2}{t}+mt)\)
如果块大小为 \(\sqrt n\), 时间复杂度为 \(O((n+m)\sqrt n)\)
如果块大小为 \(\frac{n}{\sqrt{m}}\), 时间复杂度为 \(O(n\sqrt m+m\log m)\)
所以有时候可以通过调整块大小来加速俗称调参
一类单点修改区间求和的问题
有时候我们要修改一个点, 求区间和
| 算法 | 修改 | 求和 |
|:----:|:----:|:----:|
| 树状数组 / 线段树 |\(O(log n)\)|\(O(logn)\)|
| 分块 1|\(O(1)\)|\(O(\sqrt n)\)|
| 分块 2|\(O(\sqrt n)\)|\(O(1)\)|
树状数组 / 线段树的做法很经典, 这里就不讲了
分块 1: 每次修改把对应的位置和对应的块的和 \(+1\)
分块 2: 每次修改把对应的位置和对应的块的和 \(+1\), 然后求出块内前缀和块内后缀和块的前缀和
有的人就要问了, 分块做法那么慢, 有什么用呢?
用处大着呢! 当修改次数与询问次数不平衡的时候, 我们可以做到比树状数组更优
博主曾经用莫队 + 分块 1 水过了一道 \(n=m={10}^6\) 的题跑的比 zjt 神犇的线段树合并还快
和排列有关的问题
很多问题让你求对于每一个排列 \(A\), 如果 \(\cdots\), 那么 \(\cdots\)
我们可以考虑从小到大插入这 \(n\) 个数, 插入第 \(i\) 个数时考虑这个数的贡献
用 trie 实现全部数 \(+1\), 查询全部数的异或和
我们从低位到高位建一棵 trie 树
从根开始, 交换左右子树, 然后对 \(0\) 的那棵子树执行同样的操作 (进位)
莫比乌斯反演的多组询问
\[ \begin{align} ans&=\sum_{i=1}^lc^{\gcd(i,b)}\&=\sum_{d|s}c^d\sum_{i=1}^l[\gcd(i,s)=d]\&=\sum_{d|s}c^d\sum_{i=1}^{\frac{l}{d}}[\gcd(i,\frac{s}{d})=1]\&=\sum_{d|s}c^d\sum_{i|\frac{s}{d}}\mu(i)\lfloor\frac{l}{id}\rfloor\\end{align} \]
看起来没办法化简了
这时候要枚举 \(j=id\)
\[ \begin{align} ans&=\sum_{j|s}\lfloor\frac{l}{j}\rfloor\sum_{i|j}\mu(i)c^\frac{j}{i}\\end{align} \]
设 \(f(x)=\sum_{i|x}\mu(i)c^\frac{x}{i}\)
这样 \(f(x)\) 就可以预处理出来了
一般情况
\[ \begin{align} ans&=\sum_{i=1}^n\sum_{j=1}^mf(\gcd(i,j))\&=\sum_{i=1}^{\min(n,m)}f(i)\sum_{i|j}\mu(\frac{j}{i})\lfloor\frac{n}{j}\rfloor\lfloor\frac{m}{j}\rfloor\&=\sum_{i=1}^{\min(n,m)}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor\sum_{j|i}f(j)\mu(\frac{i}{j}) \end{align} \]
这样可以预处理后面的 \(g(n)=\sum_{i|n}\mu(\frac{n}{i})f(i)\)
每次枚举前面询问
时间复杂度:\(O(n+T\sqrt{n})\)
分治 FFT
分治 FFT 一般有两个用途
求很多个多项式的乘积 (普通分治)
设有 \(n\) 个多项式, 次数之和是 \(m\), 那么时间复杂度就是 \(O(m\log m\log n)\) 一共有 \(\log n\) 层, 每层是 \(O(m\log m)\) 的
求一类数列 (CDQ 分治)
数列 \(f_n=\sum_{i=0}^{n-1}f_ig_{n-i}\) 对于一个分治区间 \([l,r]\), 先求出 \([l,mid]\) 的答案, 再计算这部分对右边 \([mid+1,r]\) 的贡献
时间复杂度:\(O(n\log^2 n)\)
矩阵快速幂 + FFT
DP 转移如下:
- \[ f_{i+1,j,k+v}+=f_{i,j,k} \]
- \(i\leq n,j\leq l,k\leq m\)
其中 \(v\) 只与 \(j\) 有关, 最后求 \(k=s\) 或 \(k\mod m=s\) 的值的和
暴力搞的时间复杂度是 \(O(l^3m^3\log n)\) 的
我们可以把这个东西看成一个多项式
\[ g_{i,j}=\sum_{k\geq 0}f_{i,j,k}x^k \]
转移就可以看成乘以一个多项式 (单项式)
如果求的是 \(k\mod m=s\) 的值的和, 就可以看成循环卷积
可以先求值, 把每个点值拿去跑一遍矩阵快速幂, 再插值回来
时间复杂度:\(O(ml^3\log n)+\) 点值插值的时间复杂度 \(O(m^2)/O(m\log m)\)
多组询问的矩阵快速幂优化 DP
设矩阵大小为 \(m\), 次数是 \(n\), 询问组数是 \(t\), 朴素的实现是 \(O(tm^3\log n)\) 的
可以先把转移矩阵的 \(i\) 次幂求出来
每次询问只需要拿一个 \(1\times m\) 的矩阵去乘转移矩阵就行了每次乘法是 \(O(m^2)\) 的
时间复杂度:\(O(m^3+tm^2\log n)\)
来源: http://www.bubuko.com/infodetail-2516774.html