AT_arc110_d [ARC110D] Binomial Coefficient is Fun
无语了无语了。
原问题等价于将一个不超过 \(m\) 的序列划分为 \(n+\sum a\) 可空段。
法一：那么答案就是 \(\sum\limits_{l=0}^{lim}\binom {l+T}T\)，观察组合意义是 \((0,0)\) 走到 \(([0,lim],T)\) 的方案数，也就是 \((0,0)\) 走到 \((lim,T+1)\) 的方案数，为 \(\binom{lim+T+1}{T+1}\)。
法二：等价于将 \(m\) 划分成 \(n+1+\sum a\) 可空段，那么直接就做完了。
总结：\(\sum\limits_{\sum\limits_{i=1}^nb_i\leqslant m}\prod\limits_{i=1}^n\binom {b_i}{a_i}=\binom{\sum\limits_{i=1}^na_i+n+m}{\sum\limits_{i=1}^na+n}\)。
AT_arc110_e [ARC110E] Shorten ABC
好厉害的计数题。
把 ABC 分别看成 123，那么合并就等同于异或！
因此，我们可以快速算出一个子串合并后会变成什么。
首先一个子串如果只有一种字母那么没法合并。
否则，子串异或和是什么合并出来就是什么。
令 \(f_i\) 表示前缀 \(i\) 的答案。考虑转移。
令 \(s_i\) 为前缀异或和，维护最近的 \(pre_j\) 满足 \(s_{pre_j}=i\)。
那么，可以得到 \(f_i=[s_i\neq 0]+\sum\limits_{j\neq i}f_j\)。
其意义为，先算上整个串压成一位的贡献，再算 \(i\) 被分到了一个区间的右端点内的贡献，注意一段子串无法为 \(0\)。
同时，这样做使得一段连续的 \(0\) 一定位于一段子串的后缀，也即 \(1331\) 只会有 \(133|1\) 的贡献，不会有 \(1|331\) 的重复贡献。
然后就好了！
AT_arc110_f [ARC110F] Esoswap
乱搞过了，来学习严谨做法。
由于 \(a_i\) 互不相同，因此，如果对于一个位置操作 \(n-1\) 次，那么这个位置会变成 \(0\)。
因为互不相同，所以一个数如果被换出去了就不会回来了。
我们对 \(n-1\) 位置这么干，那么 \(a_{n-1}=0\)。
然后，对 \(n-2\) 位置这么干。根据前面的结论，\(a_{n-2}=0\)。那在哪一次操作中 \(a_{n-2}\) 会变成 \(0\) 呢？肯定是 \(a_{n-2}=1\) 的时候了！
也许你已经发现了，这样做会导致 \(a_{[-2,-1]}=[0,1]\)。
好了，倒着做，每个位置做 \(n-1\) 次，就完了。
P5826 【模板】子序列自动机
就是对于每个 \(i\) 记录之后 \(j\) 最早出现位置进行贪心，然后直接暴力跳。
只不过预处理太大了，那么主席树优化一下就好了。
P5301 [GXOI/GZOI2019] 宝牌一大堆
喜欢！
国特殊处理，枚举哪张出现两次即可。
七对子特殊处理，设 \(g_{i,j}\) 表示处理到了第 \(i\) 类数牌已经有 \(j\) 对的最大分数，直接转移。
正常情况，首先有一个观察，因为宝牌不重复，因此杠一定劣于刻，也即一定是 \(3\times 4+2\)。
令 \(f_{i,j,c1,c2,h}\) 表示前 \(i\) 种数牌，有 \(j\) 个面子 \(h\) 个刻子，\(i-1\) 用了 \(c1\) 张，\(i-2\) 用了 \(c2\) 张的最大分数。
所有 \(i-1,i,i+1\) 的顺子都在枚举 \(i+1\) 时处理。
那么就枚举 \(i+1\) 用了几张，怎么用就好了。
- \(0\) 张：什么也不干。
- \(1\) 张：顺子。
- \(2\) 张：对子；顺子+顺子。
- \(3\) 张：对子+顺子；刻子。
- \(4\) 张：对子+顺子+顺子；刻子+顺子。
直接做就好了。
听说别人还要特判 \(\tt 8p,8s,8m,E,N,S,W,Z,F,B\) 的不能成顺子的特殊情况。
我的评价是，只要编号别连续不就好了嘛。
CF1740H MEX Tree Manipulation
很棒的题目。很牛的题目。
首先离线询问搞出树，然后树剖。
使用 lxl 经典 trick，对于一个点，重儿子和轻儿子分别维护。
对于重儿子，我们考虑维护 \(f(x)\) 表示，如果重儿子的值为 \(x\)，则自己的值为 \(f(x)\)。容易发现 \(f(x)\) 可以简单 \(O(1)\) 维护，且是可合并的。
也就是说，我们不动态维护它的值，而只维护 \(f\) 以来计算。
这个函数的修改依赖轻儿子，考虑维护轻儿子，就是对于每一个节点开一个 mex 的权值线段树，将轻儿子的权值全部放进去，以求 mex。
这样的话，单词操作复杂度就是 \(O(n\log^2n)\)
Min_25 筛
若 \(f\) 为积性函数，且 \(f(p^k)\) 是关于 \(p^k\) 的低次多项式，求 \(\sum\limits_{i=1}^nf(i)\)。
Min_25 可以做到 \(O(\frac {n^{\frac34}}{\log n})\)。它求的是 \(F(n)=\sum\limits_{i=2}^nf(i)\)。
首先要求出 \(n\) 所有的整除点 \(idx_n\)，我们要求出所有 \(idx\) 处的函数值。
令 \(S_{k,j}(n)=\sum\limits_{i=2}^ni^k[i \in \mathbb{P} \lor \operatorname{minp}(i)\geqslant p_j]\)。考虑递推求。
首先注意到 \(S_{k,1}=\sum\limits_{i=2}^ni^k\)，可以快速求。
考虑使用 \(j\) 推至 \(j+1\)，注意到要去掉 \(i\not\in\mathbb P\land \operatorname{minp}=p_j\) 的 \(i\) 贡献，得 \(S_{k,j+1}=S_{k,j}-p_j^k\left(S_{k,j}\left(\left\lfloor\frac n{p_j}\right\rfloor\right)-sump_{k,j-1}\right)\)，其中 \(sump_{k,j}=\sum\limits_{i=1}^jp_i^k\)，可以递推求。
当 \(j>\lfloor\sqrt n\rfloor\) 时，会发现 \(S_{k,j}\) 关于 \(j\) 增加而值不变了。此时 \(S_{k,j}\) 中只有质数，没有合数。
令 \(g_j(n)=\sum\limits_{i=2}^nf(i)[i \in \mathbb{P} \lor \operatorname{minp}(i)\geqslant p_j]\)，容易发现，当 \(j>\lfloor\sqrt n\rfloor\) 时可以根据 \(f\) 的表达式求得 \(g_j(n)=\sum\limits_{i=0}^{\deg f}[x^i]f(x)S_{i,j}\)。
考虑由 \(j+1\) 推至 \(j\)，注意到要加上 \(i\not\in\mathbb P\land \operatorname{minp}=p_j\) 的 \(i\) 贡献。由于 \(\frac i{p_j}\) 与 \(p_j\) 不一定互质，不能照搬求 \(S\) 的方法。
考虑枚举 \(p_j\) 出现次数 \(k\)，可以得到 \(g_{j}(n)=g_{j+1}(n)+\sum\limits_{k=1}^{p_j^{k+1}\leqslant n}\left(f(p_j^k)\left(g_{j+1}\left(\left\lfloor\frac n{p_j^k}\right\rfloor\right)-sumf_j\right)+f(p_j^{k+1})\right)\)，其中 \(sumf_{j}=\sum\limits_{i=1}^jf(p_i)\)，可以递推求。
那么 \(F(n)=g_1(n)\)，答案就是 \(F(n)+1\)。
AT_arc128_c [ARC128C] Max Dot
牛逼。
猜结论：一段为 \(0\)，一段为 \(x\)，一段为 \(m\)。然后就过了。
证明：若没有 \(m\) 的限制，那么每次我们会选择 \(\frac {suf_i}{n-i+1}\) 的一段全部填满，也就是按照这个性价比排序。
现在有了 \(m\) 的限制，考虑先填到 \(m\)，再把这个填满的后缀删掉，然后递归直到 \(s\) 被用完。不难发现答案的形式就变成那个结论了。
AT_arc128_d [ARC128D] Neq Neq
注意到若存在两个相邻的数相同，那么这两个数一定删不掉。
因此，可以根据这个把原序列分成若干段，每一段两个端点必选，方案数之积。
在一个段内，令 \(f_i\) 表示 \(i\) 必选，前 \(i\) 个数的方案数。
注意到 \(12121\cdots\) 的影响，分类讨论：
- 若 \(i\) 不在这样的段里，则中间可以任意删除，则 \(f_i=\sum\limits_{j=l}^{i-1}f_j\)。
- 若 \(i\) 在这样的段里，则中间不可任意删除，设所在的这样的 \(ababa\) 左端点为 \(d\)，则 \(f_i=f_{i-1}+f_{i-2}+\sum\limits_{j=l}^{d-1}f_j\)。
做完了。
AT_arc128_e [ARC128E] K Different Values
很牛的思维题。
首先考虑什么时候无解，一个简单的想法是存在 \(a_i>c\)，其中 \(c\) 是段数。
当然这样还是不够的，考虑这 \(c\) 个段里有 \(c-1\) 个 \(k\) 段和 \(1\) 个 \(r\in[1,k]\) 段，那么我们需要 \(a\) 中 \(c\) 的数量 \(\leqslant r\)，原因显然。
如果上面两个都满足了，可以构造出来一定有解。
考虑从前往后贪心构造，\(r\) 段在最前面。注意到如果 \(a\) 中 \(c\) 的数量 \(=r\) 了，我们就需要放那些 \(=c\) 的数，否则是随便放的。
实践出真知，这样就过了，那就过了吧。
就做完了。复杂度 \(O(n^3)\)。
AT_abc247_h [ABC247Ex] Rearranging Problem
首先，先钦定交换一定在同色进行。
在每种颜色内，子问题为排列 \(p_i\) 在交换最多 \(t\) 次后的不同方案数量。
那么一次交换会使得 \(i\to p_i\) 的图中环的数量变化恰好 \(1\)，发现一种有 \(m\) 个置换环的局面需要操作至少 \(sz-m\) 次。
注意到恰好交换 \(t\) 次的方案数为第一类斯特林数 \(m\brack t\)，有其生成函数 \(F_m(x)=x^{\overline{m}}\)。那么就把全部颜色的生成函数乘起来，设为 \(G\)。
求 \(G\) 可以分治+NTT \(O(n\log^2n)\) 求。求完之后，枚举最少需要 \(t\) 次的局面，发现 \(t\geqslant \max(n-k,1)\) 且步长为 \(2\)，暴力统计 \(\sum\limits_t[x^t]G(x)\) 即可。
CF464E The Classic Problem
标准的最短路，考虑优化比较和加法。
首先是二进制加法，考虑可以使用主席树优化。具体地，线段树记录每一位是 \(0\) 还是 \(1\)，一次加法就是单点赋 \(1\)，区间推 \(0\)，其中区推可以连到一棵 \(0\) 树上得以实现。
其次是比较，考虑找到 lcp，这里可以哈希，然后比较 lcp 的下一位是什么，就好了。
以上所有的二分均需要在线段树上二分。
CF1515F Phoenix and Earthquake
牛的。
首先有简单的无解情况，不连通，以及 \(\sum a<(n-1)x\)。
否则，我们尝试去构造一下以发现其他无解情况或者直接全都有解。
考虑一棵生成树，对于生成树上的一个叶子 \(u\)，若 \(a_u\geqslant x\) 则与父亲直接合并，然后规约到规模更小的子问题；若 \(a_x<x\)，则把这个叶子删掉，然后规约到规模更小的子问题，最后再合并这个叶子。
那么就做完了。
CF1185G2 Playlist for Polycarp (hard version)
题目就是把若干种数选个子集拿出来排列的方案数。
考虑没有限制和的时候怎么做。
令 \(f_{i,j,k,1/2/3}\) 表示为现在每种数的数量，以及末尾是什么，直接转移。
现在考虑对于每种数怎么填，考虑思维上的递推。
容易发现可以三维背包，\(g_{i,j,k,t}\) 表示填了三种各有了几个，总和为 \(t\)。然后你发现复杂度是 \(O(n^4T)\) 的，没法做，尝试优化一个 \(n\) 掉。
注意到我们并不关心 \(t<T\) 的那些值，考虑把背包拆成两半，\(g1_{i,t}\) 和 \(g2_{j,k,t}\) 两边分开做，复杂度各是 \(O(n^2T)\) 和 \(O(n^3T)\) 的。
然后这两个合并你就可以 \(O(n^3T)\) 得到 \(g_{i,j,k,T}\) 的值了。
考虑计算答案，就是 \(\sum\limits_{i,j,k}f_{i,j,k,*}\times g_{i,j,k,T}\times i!\times j!\times k!\)。
那么就做完了。
P1587 [NOI2016] 循环之美
首先要知道怎么样的 \(\frac xy\) 符合条件。
设循环节为 \(l\)，则纯循环数 \(\frac xy\) 应当满足 \(\frac xy-\lfloor\frac xy\rfloor=\frac {xk^l}y-\lfloor\frac {xk^l}y\rfloor\)。
发现这等价于 \(\frac {x(k^l-1)}y\in \Z\)，由于不能计重，就要 \(\gcd(x,y)=1\)，则 \(k^l-1\equiv 0\pmod y\)。由经典结论可得 \(\gcd(k,y)=1\)。
因此就是求 \(ans=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1]\)。
考虑化简。
\[\begin{aligned} ans&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1]\\ &=\sum\limits_{j=1}^m[\gcd(j,k)=1]\sum\limits_{i=1}^n[\gcd(i,j)=1]\\ &=\sum\limits_{j=1}^m[\gcd(j,k)=1]\sum\limits_{i=1}^n\sum\limits_{d\mid i,d\mid j}\mu(d)\\ &=\sum\limits_{j=1}^m[\gcd(j,k)=1]\sum\limits_{d=1,d\mid j}^n\left\lfloor\frac nd\right\rfloor\mu(d)\\ &=\sum\limits_{d=1}^n\left\lfloor\frac nd\right\rfloor\mu(d)\sum\limits_{j=1}^{\lfloor\frac md\rfloor}[\gcd(jd,k)=1]\\ &=\sum\limits_{d=1}^n\left\lfloor\frac nd\right\rfloor\mu(d)\sum\limits_{j=1}^{\lfloor\frac md\rfloor}[\gcd(j,k)=1][\gcd(d,k)=1]\\ &=\sum\limits_{d=1}^n\left\lfloor\frac nd\right\rfloor\mu(d)[\gcd(d,k)=1]\sum\limits_{j=1}^{\lfloor\frac md\rfloor}[\gcd(j,k)=1]\\ \end{aligned} \]令 \(f(n)=\sum\limits_{j=1}^n[\gcd(j,k)=1]\)，使用辗转相除法可得 \(f(n)=\lfloor\frac nk\rfloor\varphi(k)+f(n\bmod k)\)，可以 \(O(k\log k)\) 求出 \(f([0,k-1])\)，就可以快速求单点或者区间和了。
继续化简。
\[\begin{aligned} ans&=\sum\limits_{d=1}^n\left\lfloor\frac nd\right\rfloor\mu(d)[\gcd(d,k)=1]\sum\limits_{j=1}^{\lfloor\frac md\rfloor}[\gcd(j,k)=1]\\ &=\sum\limits_{d=1}^n\mu(d)[\gcd(d,k)=1]\left\lfloor\frac nd\right\rfloor f\left(\left\lfloor\frac md\right\rfloor\right)\\ \end{aligned} \]发现后面两项是可以整除分块的，考虑求前面两项之和。
令 \(g(n,k)=\sum\limits_{d=1}^n\mu(d)[\gcd(d,k)=1]\)。
继续化简。
\[\begin{aligned} g(n,k)&=\sum\limits_{d=1}^n\mu(d)[\gcd(d,k)=1]\\ &=\sum\limits_{d=1}^n\mu(d)\sum_{p\mid d,p\mid k}\mu(p)\\ &=\sum_{p\mid k}\mu(p)\sum\limits_{d=1,p\mid d}^n\mu(d)\\ &=\sum_{p\mid k}\mu(p)\sum\limits_{d=1}^{\lfloor\frac np\rfloor}\mu(dp)\\ &=\sum_{p\mid k}\mu(p)\sum\limits_{d=1}^{\lfloor\frac np\rfloor}\mu(dp)[\gcd(d,p)=1]&\text{as }\mu(dp)\neq 0\text{ only when }d\perp p\\ &=\sum_{p\mid k}\mu(p)\sum\limits_{d=1}^{\lfloor\frac np\rfloor}\mu(d)\mu(p)[\gcd(d,p)=1]\\ &=\sum_{p\mid k}\mu^2(p)\sum\limits_{d=1}^{\lfloor\frac np\rfloor}\mu(d)[\gcd(d,p)=1]\\ &=\sum_{p\mid k}\mu^2(p)g\left(\left\lfloor\frac np\right\rfloor,p\right)\\ \end{aligned} \]可以递归处理。
边界 \(g(0,k)=0\)。\(g(n,1)=\sum\limits_{d=1}^n\mu(d)\) 直接杜教筛。
那么就做完了，复杂度 \(O(\sqrt n\sum\limits_{p\mid k}[p\in\mathbb{P}]+n^{\frac 23})\)。
AT_arc122_e [ARC122E] Increasing LCMs
草，被薄纱了。
先分解质因数，然后可以很好判断 lcm 了，然后呢？
考虑正着做难以保证，那就倒着做，每次枚举填什么然后直接暴力判断可不可行。
然后就过了。
事实上，对于子问题也就是我们要填末尾，要求 \(\gcd(a_n,\operatorname{lcm}(a_{[1,n-1]}))\neq a_n\)，转化为 \(\operatorname{lcm}(\gcd(a_{[1,n-1]},a_n))\neq a_n\)。
所以你可以按着这个直接找，根本不需要分解质因数。
注意到条件等价于 \(\operatorname{lcm}(\gcd(a_{[1,n-1]},a_n))\neq a_n\)，随着问题规模减小左边会越来越小，因此一个数在 \(i\) 时刻若可以被填则 \([1,i-1]\) 均可以被填。
因此直接找一个能填的填上去，正确性是对的。找不到了，就无解了。
AT_arc122_f [ARC122F] Domination
首先如果一个红点在另一个红点的左下方，那么这个红点一定是没用的。
因此我们只保留有用的红点，形成一个 \(x\) 递增 \(y\) 递减的序列。
考虑一个蓝点覆盖一段红点区间，在不考虑移动时就是志愿者招募。
考虑移动，发现起点只和 \(y\) 有关，终点只和 \(x\) 有关，因此可以前缀优化建图，跑最小费用最大流即可。
多项式乘法逆
就是求 \(f^{-1}\) 满足 \(f*f^{-1}\equiv1\pmod {x^n}\)。
考虑倍增构造。
设 \(g^{-1}\)，满足 \(f*g^{-1}\equiv1\pmod {x^{\lceil\frac n2\rceil}}\)。由此可得 \(f^{-1}-g^{-1}\equiv0\pmod {x^{\lceil\frac n2\rceil}}\)。
两边平方，可得 \((f^{-1})^2-2f^{-1}g^{-1}+(g^{-1})^2\equiv 0\pmod {x^n}\)。
移项，同乘 \(f\)，可得 \(f^{-1}\equiv g^{-1}(2-fg^{-1})\pmod{x^n}\)。
那么循环构造就可以了，注意到 \(n=1\) 时 \(f^{-1}=f_0^{p-2}\)。
复杂度 \(O(n\log n)\)，需要 NTT。
P10641 BZOJ3252 攻略
长剖，然后选前 \(k\) 大的链。
做完了。
万恶的 ad-hoc。
分治 FFT
已知 \(g_{[1,n]}\)，求 \(f_{[0,n]}\)，其中 \(f_0=1,f_{i}=\sum\limits_{j=1}^if_{i-j}g_j\)。
使用分治，设我们正在算 \(f_{[l,r]}\)，那么需要 \(f_{[0,l-1]}\) 已经全部计算好。
如果 \(l=r\)，那么自动算好了。
否则，先去算 \([l,mid]\)，然后要计算 \([l,mid]\) 在 \([mid+1,r]\) 上的贡献，再算 \([mid+1,r]\) 就好了。
计算左边对右边的贡献，就是 \(f_{[mid+1,r]}\gets f_{[l,mid]}\times g_{[1,r-l+1]}\)，用 NTT 就好了。
复杂度 \(O(n\log^2n)\)。
但其实也可以用逆元 \(O(n\log n)\) 做，但这样没有拓展性。
令 \(g_0=0\)，发现 \(F\times G=\sum\limits_{i=1}^n\sum\limits_{j=0}^if_{i-j}g_j=F-f_0x^0\)。
即 \(F\equiv(1-G)^{-1}\pmod {x^n}\)。
CF1100F Ivan and Burgers
学到了，前缀线性基。
考虑扫描线，那怎么做区间上的线性基呢？
考虑我们给每一个主元记录插进来的时间，那么我们只用那些时间符合要求的就好了。
根据贪心的思想，我们想让主元的时间尽量晚。那怎么插入呢？
插入时，如果碰到了一个主元存在且比自己早，那就交换自己和主元，然后继续插入主元，这样就可以使得时间尽量晚，因为早的都被重新插进去并且插不进去了。
复杂度是 \(O(n\log n)\) 的。
P3292 [SCOI2016] 幸运数字
其实就是把前缀线性基搬到树上了，做法是一样的，插入时间就是深度。
注意查询 \((u,lca),(v,lca)\) 时两个线性基要合并，不然容易找不到答案。
P3265 [JLOI2015] 装备购买
使用到了一个重要结论：一组向量的基的大小是固定的。
因此可以直接从小到大插，正确性是对的。判断差不差的进去就是线性基的事情了，交给消元，可能是高斯消元。
P2455 [SDOI2006] 线性方程组
补了几年前留下的消元大坑。
发现在学了线性基以后这些题变得格外容易。
什么消元？那就先找一组基，上三角的那种。
然后再从下往上消元，就好了。
子集卷积
求 \(c_k=\sum\limits_{i\cup j=k,i\cap j=\varnothing}a_ib_j\)。
发现这个与 FWT 或的卷积很像，唯一不同处要求 \(i\) 与 \(j\) 没有交。
考虑把它变一下，设 \(A_{s,i}=\sum\limits_{t\in s,|t|=i}A_t\)。那么就很好做了，\(C_{s,i}=\sum\limits_{j=0}^iA_{s,j}B_{s,i-j}\)，来刻画没有交。
然后套用 OR 的 FWT 即可，复杂度 \(O(n\log^2n)\)。
多项式牛顿迭代
就是给函数 \(g\) 求多项式 \(f\) 满足 \(g(f(x))\equiv 0\pmod {x^n}\)。
考虑倍增，首先在 \(n=1\) 的时候特殊求。比如 \(g(x)=\ln x\) 时 \(f(x)=1\)。
设 \(h\) 满足 \(g(h(x))\equiv 0\pmod{x^{\lceil\frac n2\rceil}}\)。
使用泰勒展开，得到 \(g(f(x))=\sum\limits_{i=0}^{+\infty}\frac1{i!}g^{(i)}(h(x))(f(x)-h(x))^i\equiv 0\pmod {x^n}\)。
注意到 \(i\geqslant 2\) 时 \((f(x)-h(x))^i\equiv 0\pmod {x^n}\)，因此有 \(g(h(x))+g'(h(x))(f(x)-h(x))\equiv 0\pmod {x^n}\)。
也就是 \(f(x)\equiv h(x)-\frac{g(h(x))}{g'(h(x))}\)。
多项式对数
给 \(f\) 求 \(g\) 满足 \(\ln f\equiv g\pmod {x^n}\)。
对两边求导可以得到 \(g'\equiv \frac {f'}f\)。
也就是 \(g\equiv \int\frac {f'}f\mathrm dx\)。由于 \(\ln f=\int\frac{f'}f\)，解得积分常数 \(c=\ln f(0)\)。
那就好了。复杂度 \(O(n\log n)\)。
注意到当且仅当 \(c=0\) 即 \(f(0)=1\) 时存在 \(g\)，否则要么 \(c\) 是超越数要么 \(f(0)\) 是超越数，在模 \(p\) 意义下均不存在。
AT_arc142_f [ARC142F] Paired Wizards
超级厉害的题。
注意到如果我们知道一个人哪些时间点 \(t_i\) 选择了攻击，那么这个人的贡献就是 \(\sum\limits_{i=1}^ct_i-\frac{c(c+1)}2\)。
因此，我们只关心选的时间的总和以及数量。
我们可以把操作分类：
- 两个人的操作都是固定的：这种情况无需决策。
- 恰好一个人的操作是固定的：只需要另一个人决策。注意到一定是先 \(1\) 再 \(2\)，所以只要知道要 \(2\) 几次就能快速算出贡献。
- 两个人都不固定，且操作相同：也是先 \(1\) 再 \(2\) 的。
- 两个人都不固定，且操作不同：注意到一定有一个人 \(2\)，那么就是 \(2\) 给谁的问题，这种情况的 \(\sum t\) 是固定的，只需要枚举给了谁几个 \(2\)。
枚举两个人各自的决策 \(2\)，以及共同的 \(3,4\)，可以做到 \(O(n^4)\)。
注意到可以预处理两个人各自的决策，令 \(f_i\) 表示 \(3,4\) 的决策中自己已经分到了 \(i\) 个 \(2\)，自己决策中的 \(t\) 的 \(\sum\limits_{i=1}^ct_i-calc(c+i)\) 的最大值。
预处理是 \(O(n^2)\) 的，计算也是 \(O(n^2)\) 的，就过了。
AT_arc142_d [ARC142D] Deterministic Placing
超级厉害树形 dp。
首先考虑怎么样的方案合法，显然要剖成若干条长度不为 \(1\) 的链。每条链有方向，因此看成箭，其中空点在箭头，箭身和箭尾都是点。
考虑怎么样的链是合法的。手模可以发现：
- 箭尾和箭尾不能相邻，否则断点不唯一。
- 箭头和箭头不能相邻，否则操作一次后断点不唯一。
- 箭身和别的箭尾不能相邻，否则断点不为一。
- 箭身和别的箭头不能相邻，否则操作一次后断点不唯一。
考虑树形 dp，令 \(f_{u,0/1/2/3/4/5/6/7}\) 表示子树 \(u\) 的方案数，其中 \(u\) 是没箭头没箭尾的箭身/有箭头没箭尾的箭身/没箭头有箭尾的箭身/有箭头有箭尾的箭身/没箭尾的箭头/有箭尾的箭头/没箭头的箭尾/有箭头的箭尾。
然后根据合法情况大力分类讨论即可，注意箭的形态。
CF932G Palindrome Partition
使用到了 PAM 的 slink trick。
trick 就是对于 \(s\) 的所有 border，其长度集合可以划为 \(O(\log n)\) 的连续段，使得每一段都是等差数列。
证明很牛，就不会了。
考虑令 \(d_u=len_u-len_{fail_u}\)，\(slink_u\) 为上一个连续段的段尾。注意到每次新加进来一个字符时，需要更新其所在的 slink 链，且有性质所更新的 slink 链都是链底，证明不会。
如果求划分为若干回文串的方案数，本来的方程为 \(f_i=\sum f_{i-j}[s_{[i,j+1,i]} \text{ are palindromic}]\)。
考虑令 \(g_u\) 维护 \(u\) 所在的 slink 链的 \(f\) 的前缀和。那么每次转移只要 \(O(\log n)\) 枚举 slink 链就可以了。
对于这道题，将后半段翻转间隔插入前半段之后就变成偶回文串划分问题，那么在 \(g\) 上额外记录一个长度的奇偶性就可以了。
CF906E Reverses
也是 slink trick 的应用。
首先将 \(t\) 间隔插入 \(s\) 中，那么变成了偶回文串划分段数最小，其中长为 \(2\) 的段不产生贡献。
照抄即可。
注意需要输出方案，因此要记录转移点。
矩阵树定理
令邻接矩阵为 \(E\)，有向图：入度矩阵为 \(D_{in}\)，出度矩阵为 \(D_{out}\)；无向图：度数矩阵为 \(D\)。
有向图：设根为 \(r\)，任意根需要枚举 \(r\)。
\(v\to u\) 的生成树数量为 \(\det(D_{out}-E)\)。
\(u\to v\) 的生成树数量为 \(\det(D_{in}-E)\)。
无向图：生成树数量为 \(\det(D-E)\)。
以上行列式内的矩阵均需要挖掉第 \(r\) 行第 \(r\) 列，其中无向图的 \(r\) 是任意的，因为没有根。
证明貌似是需要 LGV 引理，但我不会。
如果带权，可以把权值看成重边。
注意到，矩阵树定理求的东西实际上是 \(\sum\limits_T\prod\limits_{e\in T}w_e\)，因此合理设置 \(w\) 有大用。
矩阵树定理适用条件：边权构成环，即对于 \(<w,+,\times>\)，数域 \(w\) 对 \(+\) 满足交换律和逆元，\(w\) 对 \(\times\) 满足结合律和单位元，\(w\) 对 \(+,\times\) 满足结合律。
AT_arc142_e [ARC142E] Pairing Wizards
厉害网络流！
首先不会减少，这是显然的。
设 \(b_x\geqslant b_y\)。那么对于这个限制，一定有 \(a_x\geqslant b_y,a_y\geqslant b_y\)，先把这些贡献加上。
然后未满足的限制的形式一定形如 \(a_x,a_y\in[b_y,b_x)\)。
考虑用最小割刻画这个限制，对于 \(x\) 建边 \((S,x,b_x-a_x)\)。
那怎么刻画 \(y\) 满足限制呢？
考虑使用 \((y,i)\) 表示给 \(y\) 增加 \(i\)，那么刻画这个条件连边 \(((y,i),T,1),((y,i),(y,i-1),+\infty)\)。
那么就可以连边 \((x,(y,b_x-a_y),+\infty)\) 来刻画限制。
容易发现总可以把点分为两类，一类使用前者建边刻画，一类使用后者建边刻画。
那么就做完了。
记得相同 \(x\) 的限制不要重复加。
P4336 [SHOI2016] 黑暗前的幻想乡
每条边有颜色，求边颜色各异的生成树个数。
如果没有颜色的限制，那么就是裸的无向图矩阵树定理。
那现在有颜色的限制了。
那么就容斥一下就好了。
状压容斥就好了。复杂度 \(O(n^32^n)\)。
P7451 [THUSCH2017] 杜老师
发现按照每一种质数作为一个二进制位刻画出现次数奇偶性，那么合法当且仅当异或和为 \(0\)，考虑线性基。
将所有数插入一个线性基，设线性基的大小为 \(x\)，那么答案就是 \(2^{len-x}\)，证明就是自由元任取，基随之变化成为唯一解，若不唯一则线性相关与线性基矛盾。
发现这样太大了，难以通过，考虑优化。
发现这样二进制位是 \(\pi(V)\) 的，太大了，但是在高位经常会空出来。具体地，我们可以将质数分类，\(p\leqslant\sqrt V\) 的质数正常操作。对于 \(p>\sqrt V\) 的质数，发现在同一个数内这样的数至多一个，考虑给这个质数单独处理，即若以前没出现过就记录答案，若出现过就异或上出现过的值然后正常插入。
于是这样复杂度是 \(O(\frac{\pi^2(\sqrt V)}{\omega})\)，还是过不了。
注意到当区间很长时出现过的每个质数都会被塞入线性基，因此可以找到这个临界值进行分治，发现大约在 \(2\sqrt V\) 的位置，于是 \(len\leqslant 2\sqrt V\) 时按照线性基做，\(len>\sqrt V\) 时枚举每一个不超过右端点的质数是否出现过，发现这样是可以的。
由于很长的询问都被特殊处理了，因此时间被大大降低，现在就可以过了。
P5406 [THUPC2019] 找树
最牛逼的地方就是把最优性转化成了存在性，即从大往小问是否存在方案。
注意到新定义的运算仍然是位运算，位与位之间相互独立，因此如有必要可以使用 FWT 卷积。
考虑如果这个运算时普通加法如何判定是否存在权值和为 \(t\) 的生成树。
那么就是让长为 \(v\) 的边边权设为形式幂级数 \(x^v\)，那么边权之积转换为幂级数指数之和。
最后看算出来的行列式中 \(x^t\) 的系数，就是权值和为 \(t\) 的答案。
现在变成位运算了，那就是卷积卷起来，考虑使用 FWT 优化。
发现 FWT 之后每个点之间互不影响。因此，可以 FWT 之后直接求行列式再 IFWT，就求好了。
复杂度 \(O(n^32^w)\)，注意要模大质数，要求逆元。
小心常数，小心寻址不连续，小心多余的传参。
P6624 [省选联考 2020 A 卷] 作业题
发现式子中的 \(\gcd\) 恰好为某个值是难做的，但是可以做 \(\gcd\) 包含某个值，那么就是容斥了，也就是反演。
考虑欧拉反演，则 \(\sum\limits_T(\sum w)\times \gcd=\sum\limits_T(\sum w)\times\sum\limits_{d\mid\gcd}\varphi(d)=\sum\limits_{d=1}^{V}\varphi(d)\sum\limits_T(\sum w)[d|\gcd]\)。
于是枚举 \(d\) 后面的部分就是保留 \(d\) 的倍数的边，边权设为 \(1+wx\)，然后矩阵树定理即可，答案就是一次项的系数。
复杂度应该是 \(O(Vn^3)\) 的。
AT_abc235_g [ABC235G] Gardens
组合数学，挺好的。
发现难以直接做，考虑减少限制。
如果不考虑每个位置至少放一个，那么答案就是 \(\sum\limits_{i=0}^A\binom ni\times\sum\limits_{i=0}^B\binom ni\times\sum\limits_{i=0}^C\binom ni\)。令 \(a_n=\sum\limits_{i=0}^A\binom ni\)，其他类似。
考虑如果要求至少放一个，发现可以容斥，那么可以枚举至少 \(j\) 个不放，就是 \(\sum\limits_{j=0}^n(-1)^j\binom nja_{n-j}b_{n-j}c_{n-j}\)。
然后预处理一下 \(a,b,c\) 就可以做到 \(O(n)\) 了。
不难发现，由于 \(\binom ni=\binom {n-1}i+\binom {n-1}{i-1}\)，即 \(a_n=a_{n-1}+a_{n-1}-\binom {n-1}A+\binom{n-1}{-1}=2a_{n-1}-\binom{n-1}A\)，\(a_0=1\)。
P9041 [PA2021] Fiolki 2
很厉害的题。
发现要求不相交路径，可以往 LGV 上想。
但这不是平面图，LGV 也只能求路径组权值积带符号和，怎么办？
考虑模一个大质数，给每条边赋一个随机边权，通过拓扑排序算出 \(k\) 个关键点到每个点的路径组权值积之和，在每个点形成一个 \(k\) 维向量 \(a\)。
有什么用呢？
如果两个终点无论如何选起点，如何选路径，路径一定相交，那么这两个终点的 \(a\) 线性相关。
证明就考虑交点为 \(u\)，一定相交就说明一定经过 \(u\)，那么 \(a_{t1}=k_1a_u,a_{t2}=k_2a_u\)，就线性相关了。
那是否 \(a\) 线性相关时就一定相交呢？其实不一定，但在模大质数的前提下发生的概率极小，可以忽略。
那么到这里其实已经差不多了，快速查线性相关就直接用线性基就好了，需要查区间线性基就直接前缀线性基即可。
复杂度 \(O(nk^2+mk)\)。
P3317 [SDOI2014] 重建
发现有恰好的限制，这个概率是难搞的。
因为此时的式子是 \(\sum\limits_T\prod\limits_{e\in T}w_e\prod\limits_{e\not\in T}(1-w_e)\)。
那就把 \((1-w_e)\) 提出来，变成 \(\left(\prod(1-w_e)\right)\sum\limits_T\prod\limits_{e\in T}\frac {w_e}{1-w_e}\)，后面用矩阵树就好了。
在 \(w_e=1\) 的时候会出问题，那么考虑可以令 \(w_e=1-\epsilon\)，这样就不会出问题了。
P3328 [SDOI2015] 音质检测
简单矩阵乘法。
注意到如果算一项是容易的，那算两项呢？
考虑把其中一项的矩阵转置，那么就是 \(Aab^TB^T\) 的结果了，直接维护就好了。
注意常数。
当然还有方法就是把所有要算的东西全部塞到一个矩阵内，但这样有点蠢。
P3193 [HNOI2008] GT考试
如果是一般的 dp，怎么做呢？
考虑一个 \(O(nm)\) 的 dp，令 \(f_{i,j}\) 为长度为 \(i\) 的串 \(t\)，后缀与 \(s\) 前缀匹配长度为 \(j\) 的方案数。
类似 kmp，\(j\) 可能会在一次操作后转移到一些位置，我们令 \(g_{j,k}\) 表示 \(j\) 转移到 \(k\) 的方案数，其中 \(j,k\neq m\)。
那么可以写出转移方程 \(f_{i+1,k}=\sum\limits_{j=1}^mf_{i,j}g_{j,k}\)。
于是惊恐地发现这可以被写成 \(vA^n\) 矩阵加速，然后就做完了。
斯特林反演
来学习组合数学了！
在学反演之前，先学一下斯特林数。
-
第一类斯特林数 \(n\brack m\) 为 \(n\) 个数分成 \(m\) 个轮换的方案数。
有递推式 \({n\brack m}={n-1\brack m-1}+(n-1){n-1\brack m}\)，边界为 \({n\brack0}=[n=0]\)。
-
第二类斯特林数 \({n\brace m}\) 为 \(n\) 个数分成 \(m\) 个无标号集合的方案数。
有递推式 \({n\brace m}={n-1\brace m-1}+m{n-1\brace m}\)，边界为 \({n\brace 0}=[n=0]\)。
剩下的斯特林数知识以后再学吧目前这些应该已经够用了。
在学习反演之前，首先要证明一些恒等式。
- \(n^m=\sum\limits_{k=0}^m{m\brace k}\binom nkk!\)
证明考虑使用组合意义，把 \(m\) 个不同的球放入 \(n\) 个不同的箱子，\(k\) 枚举的是有几个箱子非空。
- 反转公式 \([n=m]=\sum\limits_{k=m}^n(-1)^{n-k}{n\brack k}{k\brace m}\)
证明的话可以考虑下降幂转普通幂 \(x^{\underline n}=\sum\limits_{i=0}^n(-1)^{n-i}{n\brack i}x^i\)。
代入 \(x^i\)，可以得到 \(x^{\underline n}=\sum\limits_{i=0}^n(-1)^{n-i}{n\brack i}\sum\limits_{k=0}^i{i\brace k}\binom xkk! =\sum\limits_{k=0}^nx^{\underline k}\sum\limits_{i=k}^n(-1)^{n-i}{n\brack i}{i\brace k}\)。
使用类似于形式幂级数的系数比较，可以得到 \(\sum\limits_{i=k}^n(-1)^{n-i}{n\brack i}{i\brace k}=[k=n]\)。
- 反转公式 \([n=m]=\sum\limits_{k=m}^n(-1)^{n-k}{n\brace k}{k\brack m}\)
证明的话可以考虑下降幂转上升幂 \(x^{\underline n}=(-1)^n(-x)^{\overline n}\) 和上升幂转普通幂 \(x^{\overline n}=\sum\limits_{i=0}^n{n\brack i}x^i\)。
考虑 \(x^m=\sum\limits_{k=0}^m{m\brace k}\binom xkk! =\sum\limits_{k=0}^m{m\brace k}x^{\underline k}=\sum\limits_{k=0}^m{m\brace k}(-1)^k(-x)^{\overline k}=\sum\limits_{k=0}^m{m\brace k}(-1)^k\sum\limits_{i=0}^k{k\brack i}(-x)^i=\sum\limits_{i=0}^mx^i\sum\limits_{k=i}^m(-1)^{i-k}{m\brace k}{k\brack i}\)。
使用系数比较，可以得到 \(\sum\limits_{k=n}^m(-1)^{i-k}{m\brace k}{k\brack n}=[n=m]\)。
接下来是斯特林反演。
\[f_n=\sum_{i=0}^n{n\brace i}g_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}{n\brack i}f_i \]\[f_n=\sum_{i=0}^n{n\brack i}g_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}{n\brace i}f_i \]证明考虑使用反转公式即可。
同时，仿照二项式反演，容易得到
\[f_k=\sum_{i=k}^n{i\brace k}g_i\Leftrightarrow g_k=\sum_{i=k}^n(-1)^{i-k}{i \brack k}f_i \]\[f_k=\sum_{i=k}^n{i\brack k}g_i\Leftrightarrow g_k=\sum_{i=k}^n(-1)^{i-k}{i \brace k}f_i \]加上两条二项式反演，我愿称之为组合数学反演六则。
发现反演的核心是反转公式，联想：二项式反演是否也有一个反转公式？
- 猜的，\([n=0]=\sum\limits_{k=0}^n(-1)^k\binom nk\)
都扯到斯特林数了，那就顺便说说普通幂和上升幂和下降幂相互转化吧。
- 普通幂转上升幂 \(x^n=\sum\limits_{k=0}^n(-1)^{n-k}{n\brace k}x^{\overline k}\)
- 普通幂转下降幂 \(x^n=\sum\limits_{k=0}^n{n\brace k}x^{\underline k}\)
- 上升幂转普通幂 \(x^{\overline n}=\sum\limits_{k=0}^n{n\brack k}x^k\)
- 下降幂转普通幂 \(x^{\underline n}=\sum\limits_{k=0}^n(-1)^{n-k}{n\brack k}x^k\)
- 上升幂转下降幂 \(x^{\overline n}=(-1)^n(-x)^{\underline n}\)
- 下降幂转上升幂 \(x^{\underline n}=(-1)^n(-x)^{\overline n}\)
好美妙的对称啊！
P10591 BZOJ4671 异或图
令 \(f_i\) 表示钦定 \(i\) 个点集之间两两无边，\(g_i\) 表示恰好有 \(i\) 个连通块，那么可以得到
\[f_i=\sum_{j=i}^n{j\brace i}g_j \]其中 \(j\) 枚举的就是实际上有 \(j\) 个连通块，那么式子的正确性就显然了。
施之以斯特林反演，可得 \(g_i=\sum\limits_{j=i}^n(-1)^{j-i}{j\brack i}f_j\)。
则答案为 \(g_1=\sum\limits_{j=1}^n(-1)^{j-1}(j-1)!f_j\)。
考虑如何快速计算 \(f\)。
发现 \(n\) 很小，可以枚举 \(n\) 的所有划分方式，那么规模是贝尔数级别的。
设分成了 \(m\) 个集合，那么对于每一条连了不同连通块的边 \(v\)，对于选的图们 \(\{G_i\}\) 需要满足第 \(v\) 位上的异或和为 \(0\)。
也就是可以把所有图全部插到只有 \(\{v\}\) 这些位的线性基里面去，设线性基的秩为 \(c\)，那么就有 \(2^{m-c}\) 的方案数。
复杂度 \(O(\text{Bell}(n)n^4)\)。
CF571D Campus
秒了一半，想到了对两维分别做并查集，一棵维护带时间戳的加标记，一棵维护 \(0\) 标记时间戳。
然后在查询上寄掉了。
其实直接使用按秩合并，然后查询就可以暴力跳了。
在加标记树上使用二分查找，就可以做到跑不满的 \(O(n\log^2n)\)。
但此时你会发现你跳到一个节点，你不知道这个标记是你合并前加的还是合并后加的，显然我们只能算合并后加进去的那部分。
那我们记录每个节点合并的时间戳，一个节点的有效部分的时间戳必须大于等于一路跳上来的合并时间戳的最大值。
当然你会发现合并的时间戳是单调增的，可以直接去孩子的时间戳。
注意合并的时候有一些细节。
多项式 exp
因为是求零点，所以我们可以 由 \(e^{f(x)}\equiv g(x)\) 得到 \(f(x)-\ln g(x)\equiv 0\)。
使用多项式牛顿迭代可得 \(g(x)=g_0(x)-\frac{\ln g_0(x)-f(x)}{\frac {1}{g_0(x)}}=g_0(x)(1+f(x)-\ln g_0(x))\)。
复杂度 \(O(n\log n)\)。
补充：互逆定理
若 \(f_0=0\) 则 \(f=\ln e^f\)。
若 \(f_0=1\) 则 \(f=e^{\ln f}\)。
P4389 付公主的背包
很牛的生成函数题。
首先容易写出背包的转移方程：\(f'_i=\sum\limits_{t=0}^mf_{i-tv}\)。
写成卷积的形式，就是 \(f'=f\times g_v\)，其中 \(g_{v,i}=[v\mid i]\)。
写成生成函数的形式，就是 \(F'=F\times G_v\)，其中 \(G_v(x)=\sum\limits_{i=0}^{+\infty}x^{v_i}=\frac 1{1-x^v}\)。
那么答案就是 \(F=\prod\limits_{i=1}^nG_{v_i}\)。
如果直接做多项式求逆，复杂度是爆炸的，大概是 \(O(m^2\log m)\)。
考虑优化，两边去对数，得到 \(\ln F=\sum\limits_{i=1}^n\ln \frac 1{1-x^{v_i}}\)。
注意到有恒等式 \(\ln \frac 1{1-x^t}=\sum\limits_{i=1}^{+\infty}\frac 1ix^{it}\)，证明下附。
那么右边就可以暴力 \(O(m\log m)\) 算出来。
然后多项式 exp 就可以了。复杂度 \(O(m\log m)\)。
证明式子 \(\ln \frac 1{1-x^t}=\sum\limits_{i=1}^{+\infty}\frac 1ix^{it}\)。
令 \(f(x)=\frac 1{1-x^t}\)。
由于 \(\sum\limits_{i=0}^{+\infty}ix^i=\frac x{(1-x)^2}\)。
则有
\[\begin{aligned} &\ln \frac1{1-x^t}\\ =&\ln f(x)\\ =&\int \frac{f'(x)}{f(x)}\text{d}x\\ =&\int (1-x^t)f'(x)\text{d}x\\ =&\int (1-x^t)(-\frac1{(1-x^t)^2})(-tx^{t-1})\text{d}x\\ =&\int (1-x^t)tx^{-1}(\frac{x^t}{(1-x^t)^2})\text{d}x\\ =&\int (1-x^t)tx^{-1}\sum_{i=0}^{+\infty}ix^{ti}\text{d}x\\ =&\int x^{-1}\sum_{i=0}^{+\infty}tix^{ti}-x^{t-1}\sum_{i=0}^{+\infty}tix^{ti}\text{d}x\\ =&\int x^{-1}\sum_{i=1}^{+\infty}tix^{ti}-x^{-1}\sum_{i=1}^{+\infty}t(i-1)x^{ti}\text{d}x\\ =&\int x^{-1}\sum_{i=1}^{+\infty}tx^{ti}\text{d}x\\ =&\int \sum_{i=1}^{+\infty}tx^{ti-1}\text{d}x\\ =&\sum_{i=1}^{+\infty}\frac 1ix^{ti}\\ \end{aligned} \]多项式开根
给 \(f\) 满足 \(f_0=1\)，求 \(g\) 使得 \(g^2=f\)。
发现两边取对数就是 \(\ln g=\frac12\ln f\)。
那么 \(g=\exp(\frac12\ln f)\)，就好了，复杂度 \(O(n\log n)\)，卡我常。
多项式除法
给定 \(f,g\) 满足 \(\deg f > \deg g\)，求 \(q,r\) 满足 \(\deg g > \deg r,f=g\times q+r\)。
令 \(f_r\) 为 \(f\) 各项系数翻转之后的函数，也就是 \(f_r(x)=f(\frac 1x)\times x^{\deg f}\)。
容易发现，由于 \(f(\frac 1x)=g(\frac 1x)\times q(\frac 1x)+r(\frac 1x)\)，可以得到 \(f_r(x)=g_r(x)\times q_r(x)+r_r(x)\times x^{\deg f-\deg g+1}\)。
也就是 \(r_r(x)\equiv \frac{f_r(x)}{g_r(x)}\pmod {x^{\deg f-\deg g+1}}\)。
注意到此时恰好有 \(\deg q=\deg f-\deg g=\deg f-\deg g+1-1\)，因此这样就可以直接求出来 \(q\) 了，进而求出 \(r\)。
多项式多点求值
给 \(f\) 和若干个 \(x_i\) 求所有的 \(y_i=f(x_i)\)。
首先注意到 \(f(x)\equiv f(x_0)\pmod {(x-x_0)}\)。
证明的话考虑 \(f(x)=g(x)(x-x_0)+h(x)\)，其中 \(\deg h<\deg (x-x_0)\Rightarrow \deg h=0\)。于是上式显然成立了，因为 \(f(x_0)=h\)。
由此，我们可以令 \(r_{l,r}(x)=f(x)\bmod (\prod\limits_{i=l}^r(x-x_i))\)，则有 \(r_{i,i}(x_i)=f(x_i),\deg r_{i,i}=0\)。
考虑分治求 \(r_{l,r}\)。
令 \(h_{l,r}=\prod\limits_{i=l}^r(x-x_i),f_{l,r}=f\bmod h_{l,r}\)，则 \(r_{l,r}=f_{l,r}\)。
预处理出 \(h\)，由 \(f_{l,mid}\equiv f_{l,r}\pmod {(x-x_i)},i\in[l,r]\) 可以分治求 \(f\)。
复杂度 \(O(n\log^2n)\)。
注意卡常，在 \(\deg f_{l,r}\) 较小的时候可以直接秦九韶求出来。
多项式快速插值
给 \(n\) 组 \((x_i,y_i)\) 求 \(n-1\) 次多项式 \(f\) 满足 \(f(x_i)=y_i\)。
容易得到 \(f(x)=\sum\limits_{i=1}^ny_i\prod\limits_{j\neq i}\frac{x-x_j}{x_i-x_j}\)。
这样算至少是 \(O(n^2)\) 的，考虑优化。
有 \(f(x)=\sum\limits_{i=1}^n\frac {y_i}{\prod\limits_{j\neq i}(x_i-x_j)}\prod\limits_{j\neq i}(x-x_j)\)。
令 \(g(x)=\prod\limits_{j=1}^n(x-x_j)\)，那么就有 \(\prod\limits_{j\neq i}(x_i-x_j)=\lim\limits_{x\to x_i}\frac {g(x)}{x-x_i}=g'(x_i)\)，用到了洛必达法则。
那么 \(f(x)=\sum\limits_{i=1}^n\frac{y_i}{g'(x_i)}\prod\limits_{j\neq i}(x-x_j)\)，后面这一坨可以分治求出来。
用到了多项式多点求值，复杂度 \(O(n\log^2n)\)。
注意常数。
多项式快速幂
常数项为 \(1\) 时就是先 \(\ln\) 再乘再 \(\exp\) 就好了。
关于指数 \(k\) 为什么模的是 \(p\) 而不是 \(p-1\)，原因就是多项式没有欧拉定理但有泰勒展开，\(e^{kx}\) 展开之后对 \(p\) 取模的正确性就显然了。
不唯一呢？考虑变成一，除以常数项即可。
那常数项为 \(0\) 呢？那就找到第一项不为 \(0\) 的，降次再升次就好了。
注意升次的时候乘上的某一项系数的 \(k\) 次中 \(k\) 是对 \(\varphi (p)\) 取模，用到了欧拉定理。
注意常数项为 \(0\) 时降次再升次时若 \(k\) 很大但取模后很小时会出问题，需要特判。
CF710F String Set Queries
非常厉害的想法。
首先这个东西是难以维护的，又要插又要删又要查。
但注意到给字符串带权，那么就只有插入没有删除了。
发现每次插一个字符串进去重构是 \(O(\sum |s|)\) 的，难以接受，归根结底是因为自动机里有太多的串。
考虑拆成 \(\log\) 个自动机，第 \(i\) 个自动机里保存 \(2^i\) 个串的信息。
如果遇到要插入一个串，就从低到高合并自动机就好了。查询的时候每个自动机全部查询一遍就好了。
由于这样每个串至多被插入 \(O(\log m)\) 次，所以是对的。
复杂度 \(O(\sum |s|\log m)\)。
P3041 [USACO12JAN] Video Game G
自动机上跑 dp，也就是 dp 套 dp，秒了。
可以开大文本串长度，可以做矩乘优化。
CF432D Prefixes and Suffixes
就是求所有 border 的出现次数。
失配树上跳，出现次数就是子树大小，没了。
AT_arc127_b [ARC127B] Ternary Strings
显然 \(2\) 开头后面跟三进制从小到大。那么怎么构造 \(0,1\) 呢？
赛时直接在这里寄了。但实际上，你就怎么构造 \(2\) 怎么构造 \(0,1\) 就好了，数字轮换映射。
AT_arc127_d [ARC127D] Sum of Min of Xor
赛时想到了这个从高到低处理，对于 \(i\) 和 \(j\) 的 \(a,b\) 最高位情况分讨：
- \((0,0),(0,1)\) 取 \(a\)。
- \((0,0),(1,0)\) 取 \(b\)。
- \((1,1),(1,0)\) 取 \(a\)。
- \((1,1),(0,1)\) 取 \(b\)。
- \((0,0),(1,1)\) 和 \((1,0),(0,1)\) 不确定，需要向下处理。
场上到向下处理不会了。
笑点解析：不会向下处理。
建什么 trie 啊，不用建。暴力做复杂度是对的啊。
AT_arc127_e [ARC127E] Priority Queue
问的是 \(s\) 长什么样，发现枚举操作容易计重，直接枚举 \(s\) 长什么样。
使用一些极强的注意力后，可以观察到：\(s_i\) 的每一位取值范围都形如一个区间。证明的话考虑删除的数是一个形如 \([r,n]\) 的区间，这个是好想的，显然如果能删除 \(r\) 就能删除 \(>r\)。下界的话显然。
好了那么处理出上下界再 \(O(n^2)\) dp 一边就做完了。
用心感受。
AT_arc127_f [ARC127F] ±AB
首先在 \(m\) 比较大的时候，根据那个啥定理，应该是全取，当 \(m\geqslant a+b-1\) 时答案就是 \(m+1\)，因为区间长度至少为 \(a+b\)，难以卡死。
反之，我们可以一直 \(+a\)，直到加不了，再 \(-b\)，再一直 \(+a\)，循环往复，直到无法操作。
无法操作时一定有 \(m-a<x<b\)，把此时的总操作次数算出来，就是这种情况会算到的数了。
假设我们已经能算出这样情况的方案数了，那么对于 \(-a,+b\) 是同样的，注意没有算上不操作的情况，以及两种情况一定不交。因为交了就一定有环，有环就有 \(m\geqslant a+b-1\)。
现在全力攻操作次数，设为 \(k\)。
如果 \(v\bmod b+a>m\)，那么 \(k=\lfloor \frac vb\rfloor\)，因为你加不了任何 \(a\)。
否则，现在需要找到最小的 \(k'\)，满足 \((v+k'a)\bmod b\in[m-a+1,b-1]\)，然后用 \(k'\) 求出 \(k=k'+\lfloor\frac{v+k'a}b\rfloor\)。
首先 \(v\bmod b+k'a\bmod b<b\)，因为如果 \(\geqslant\) 的话，就有 \((v+k'a)\bmod b+a<v\bmod b+a\leqslant m\)，与无法操作不符。
那么就可以变成 \(k'a\bmod b\in[m-a+1-(v\bmod b),b-1-(v\bmod b)]\)。
考虑解这个东西 \(k'a\bmod b\in [l,r]\)。
首先，如果有 \(\left\lfloor\frac{l-1}a\right\rfloor\neq\left\lfloor\frac{r}a\right\rfloor\)，那么就可以轻松算出最小值 \(k'=\left\lceil\frac la\right\rceil\)。
否则的话，考虑使用类欧代换 \(b=a\lfloor\frac ba\rfloor+b\bmod a\)。
可以得到
\[\begin{aligned} k'a\bmod b&\in[l,r]\\ k'a-b\left\lfloor\frac{k'a}b\right\rfloor&\in[l,r]\\ k'a-\left(a\left\lfloor\frac ba\right\rfloor+b\bmod a\right)\left\lfloor\frac{k'a}b\right\rfloor&\in[l,r]\\ \left(b\bmod a\right)\left\lfloor\frac{k'a}b\right\rfloor&\in[a\left(k'-\left\lfloor\frac ba\right\rfloor\left\lfloor\frac{k'a}b\right\rfloor\right)-r,a\left(k'-\left\lfloor\frac ba\right\rfloor\left\lfloor\frac{k'a}b\right\rfloor\right)-l]\\ \left(b\bmod a\right)\left\lfloor\frac{k'a}b\right\rfloor\bmod a&\in[(a-r\bmod a)\bmod a,(a-l\bmod a)\bmod a]\\ \end{aligned} \]递归计算 \(\left\lfloor\frac{k'a}b\right\rfloor=t\) 即可，然后可以得出 \(k'a\in[l+bt,r+bt]\)，可以算出来 \(k'=\left\lceil\frac {l+bt}a\right\rceil\)。辗转相除法复杂度 \(O(\log V)\)。
然后就做完了。
CF1063F String Journey
首先，翻转串，因为好看。如果把 \(t\) 限制成 \(|t_{i+1}|=|t_i|+1\Rightarrow |t_i|=i\)，显然不劣。
发现答案上界是 \(O(\sqrt n)\) 的，那么可以令 \(f_{i,j}\) 表示做到了 \(i\) 且选了 \(i\)，答案为 \(j\) 是否存在。
转移的话就是在当前字符串上去头或者去尾就可以了，可以哈希。
复杂度 \(O(n\sqrt n)\)，人傻常数大。
卡常就别用太大的模数了吧。。
P3290 [SCOI2016] 围棋
考虑状压。不会轮廓线怎么办呢。
首先把至少一个容斥成一个都没有，考虑计数。
发现你根本不关心上一行长什么样，只关心上一行哪些位置完全匹配了。那么就只记录这个。
枚举这一行长什么样，那么可以得出上一行的状态应该是某个集合的子集，用高位前缀和优化一下就好了。
复杂度 \(O(qn3^m+qn(m-c+1)2^{m-c+1})\)。
标签：选写,lfloor,frac,limits,sum,rfloor,杂题,left From： https://www.cnblogs.com/luanyi/p/18579124