六月 & 七月杂题选做

大数定律$:$ $\lim\limits_{n->\infty} \sum\limits_{i=1}^{n} a_i \times (\frac{1}{n}) = E(a_i)$ --- [P5296 [北京省选集训2019]生成树计数](https://www.luogu.com.cn/problem/P5296) 把边权 $w$ 变成 $e^{wx}$ 然后求一下在 $\pmod{x^{k+1}}$ 意义下的行列式即可 $.$ 因为 $k$ 比较小 $,$ 所以求逆和多项式乘法只能写$O(k^2)$ $,$ 直接套多项式板子会变慢 $.$ 复杂度 $O(n^3k^2).$ --- [P3746 [六省联考2017]组合数问题](https://www.luogu.com.cn/problem/P3746) 循环卷积快速幂$.$ 感觉和2020年联考A卷 d1t2 很像? 因为我当场做那个题的时候也是用的组合意义. $O(k^2(\log n+\log k))$ --- [CF474F Ant colony](https://www.luogu.com.cn/problem/CF474F) 线段树维护区间$gcd,min$以及$cntmin$即可$.$ 如果写了$O(n)-O(1)$ $\gcd$ 可以做到一个 log. --- [CF585F Digits of Number Pi](https://www.luogu.com.cn/problem/CF585F) 建$SAM/AC$自动机之后数位$dp.$ 我代码里写的是$SAM,$因为这样省空间$.$ $O(nd^2*10)$ ~~每天一个爆零小技巧 : 计算 trans 不 return~~ --- [P5308 [COCI2019] Quiz](https://www.luogu.com.cn/problem/P5308) $wqs$二分+斜率优化 $O(n*T),T$为$check$次数$.$ ~~每天一个爆零小技巧 : 斜率优化不弹队首~~ --- [P5488 差分与前缀和](https://www.luogu.com.cn/problem/P5488) 差分一次相当于和 $(1-x)$ 卷积 前缀和一次相当于和 $(1-x)^{-1}$ 卷积 注意到 $(1-x)^k$ 的 $i$ 次项系数是 $(-1)^{i}\binom{k}{i}$ $(1-x)^{-k}$ 的 $i$ 次项系数是 $\binom{k+i-1}{i}$ $($ 这个可以通过广义二项式定理证明 $)$ 然后直接$O(n)$递推出所有系数$,$然后$NTT$就解决了$.$ ~~每天一个爆零小技巧 : 在 $k$ 是 $10^{2328}$的时候读入优化不取模~~ --- [CF685C Optimal Point](https://www.luogu.com.cn/problem/CF685C) 先二分答案然后换元解方程$,$细节比较多$.$ --- [CF708E Student's Camp](https://www.luogu.com.cn/problem/CF708E) 考虑一个$\large dp_{i,l,r}$表示目前到第$i$行$,$这一行的区间为$[l,r]$的方案数$.$ 再记一个$\large sum_{i,L}$表示 $\large \sum\limits_{l',r'\leq L} dp_{i,l,r}$ 然后推一推式子就可以$O(nm)$求出所有的$sum_{i,L},$这个问题就解决了$.$ --- [CF698D Limak and Shooting Points](https://www.luogu.com.cn/problem/CF698D) 暴力枚举打的顺序然后$bfs$ $check.$ $O(n \times k!\times k)$ --- [CF521E Cycling City](https://www.luogu.com.cn/problem/CF521E) 在$dfs$树上如果有两个相交的环$,$那么必然有解$：$ $1.$ $e1_x->e1_y->x$ $2.$ $e1_x->e2_x->e2_y->x$ $3.$ $e1_x->x$ --- [P3747 [六省联考2017]相逢是问候](https://www.luogu.com.cn/problem/P3747) 首先可以想到通过欧拉定理计算$.$ 不难发现只有前$log$次修改是有用的$,$那么直接维护就可以了$.$ 实现的好可以做到$O(nlog^2max(p,n))$ --- [CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths](https://www.luogu.com.cn/problem/CF741D) $dsu$ $on$ $tree$ 练习题$.$ 大概就是把字母$x$的权值看成$2^{x-'a'},$然后$check$一条链合法相当于链上异或和为$0$或$2^h,$ $dsu$ 一下就好了 $.$ $O(n\log n*22),$需要$O(2^{22})$的空间 --- [CF643G Choosing Ads](https://www.luogu.com.cn/problem/CF643G) 感觉这个套路已经做了一万次了吧.. 线段树维护信息$,$每次删去 $\lfloor \frac{100}{p} \rfloor +1$ 个不同的数 $,$ 最后剩下的 $k$ 种数中必然包含答案$.$ 记 $k = \lfloor \frac{100}{p} \rfloor +1,$ 复杂度为 $O(nk^2logn)$ --- [P3224 [HNOI2012]永无乡](https://www.luogu.com.cn/problem/P3224) 线段树合并$/$启发式合并板子题$.$ --- [CF1364E X-OR](https://www.luogu.com.cn/problem/CF1364E) 交互题$.$ --- [CF536D Tavas in Kansas](https://www.luogu.com.cn/problem/CF536D) 先求完最短路$,$然后$O(n^2) dp.$ --- [CF611G New Year and Cake](https://www.luogu.com.cn/problem/CF611G) 计算几何题$.$ 考虑求出凸包然后在凸包上$O(n)$扫$($ 类似$2-pointers,$ 同时维护面积大小 $),$ 然后用前缀和快速计算答案 $.$ --- [CF527E Data Center Drama](https://www.luogu.com.cn/problem/CF527E) 欧拉回路题$.$ 突然发现自己以前写的欧拉回路复杂度是假的$!$ $O(nlogm)$ ~~每天一个爆零小技巧 $:$ 在交题之前一不小心 shift + delete + enter 删掉自己的代码~~ --- [CF587D Duff in Mafia](https://www.luogu.com.cn/problem/CF587D) 首先忽略边权$,$考虑求一组可行的方案$.$可以使用$2-SAT$实现$,$建图需要前后缀优化$.$ 加上边权的限制就是加一个二分$.$ 强制让一个东西不能选就是加一条 $(x,1)->(x,0)$ 的边$.$ $O(mlogm),$实现的时候注意节省空间$.$ 我的代码是$|V|\leq 7m,$ $|E| \leq 17m$ --- [CF516D Drazil and Morning Exercise](https://www.luogu.com.cn/problem/CF516D) 不难发现权值分布组成了一棵以$f_x$最小的$x$为根的树$,$其中父亲的权值一定$\leq$儿子的权值$.$ 那么直接$two-pointers,$然后用并查集维护当前的答案就可以做到 $O(nα(n))$处理一组询问 $.$ 复杂度 $O(nα(n)q).$ --- [CF605E Intergalaxy Trips](https://www.luogu.com.cn/problem/CF605E) 考虑倒着做$,$从小到大更新概率$,$并维护不出现边的概率和出现边时的期望$.$ $O(n^2)$, --- [P3825 [NOI2017]游戏](https://www.luogu.com.cn/problem/P3825) $2-SAT.$ 枚举类型为```x```的场地的类型然后$2-SAT$即可$.$ $O(2^d(n+m))$ --- [CF538H Summer Dichotomy](https://www.luogu.com.cn/problem/CF538H) 贪心的考虑$n1,n2$的取值然后二分图染色即可$.$ $O(n+m)$ --- [CF571D Campus](https://www.luogu.com.cn/problem/CF571D) 对$M$操作带来的合并建树$,$并用$dfs$序建线段树$,$可以求出一个数最近的$Z$操作的时间$,$这样我们把询问差分成两个前缀询问$,$用启发式合并维护一下就可以了$.$ $O(n\log n),$注意这题的空间限制$,$尽量不要用空间带$log$的做法$.$ --- [P6630 [ZJOI2020] 传统艺能](https://www.luogu.com.cn/problem/P6630) 矩乘题$.$ --- [CF568C New Language](https://www.luogu.com.cn/problem/CF568C) $2-SAT+$贪心$.$ $O(nm).$ --- [CF566E Restoring Map](https://www.luogu.com.cn/problem/CF566E) 首先非叶节点之间的边可以直接集合之间两两取$and$得到$.$ 然后特判掉非叶节点个数$\leq 2$的情况$,$叶节点$>3$个的时候可以通过比较$bitset$得到叶节点的父亲$.$ $\large O(\frac{n^3}{w}),$其中$w=64.$ --- [CF603E Pastoral Oddities](https://www.luogu.com.cn/problem/CF603E) 不难发现题目中的条件等价于所有联通块大小都是偶数$.$ 可以用$lct$维护最小生成树$,$也可以分治$.$ $O((n+m)\log(n+m))$ 或 $O(n\log n \log m),$ 但在实际效果上分治比 $lct$ 快 $.$ --- [CF585E Present for Vitalik the Philatelist](https://www.luogu.com.cn/problem/CF585E) 考虑求出$f_d =$ $[\gcd \{ S \} = d$的 $\{ S \}$ 的数量 $],$ 和 $g_d = $ $ [ $ $ x \perp d $ 的 $x$ 的数量 $ ] ,$ 那么答案为 $ans =\sum\limits_{i>2}^{10^7} f_ig_i$ 可以反演之后 [$Dirichlet$ 前缀和](https://www.luogu.com.cn/problem/P5495) , $O(w\log \log w)$ --- [P5787 二分图 /【模板】线段树分治](https://www.luogu.com.cn/problem/P5787) 线段树分治 $/$ $\ LCT.$ --- [CF576E Painting Edges](https://www.luogu.com.cn/problem/CF576E) 线段树分治$,$当一个操作生效之后把它$insert$到线段树上即可$.$ $O(n\log^2n+nk)$ 需要注意的是 $,$ 理论上是可以用 $lct$ 维护这个东西的 $,$ 但是如果使用 $lct$ 来维护会爆空间 $.$ --- [CF553E Kyoya and Train](https://www.luogu.com.cn/problem/CF553E) 首先有一个$O(mt^2)$的暴力$,$然后容易发现转移是一个卷积的形式$,$并且转移图是一个$DAG.$ 那么就可以分治$FFT$解决这个问题了 $.$ $O(mt\log ^2t).$ --- [CF643F Bears and Juice](https://www.luogu.com.cn/problem/CF643F) 一道好题$.$ 我们从信息熵的角度去考虑问题$,$即在这样一个问题中会有多少种熊醉酒情况$($ 在哪一天喝醉以及是否喝醉 $),$ 这个数值 $Ans=\sum \binom{n}{i}\times x^i$ $(x$表示天数$),$不难发现这个数值是答案的上界$.$ 并且我们可以构造出对应的方案使得在有$Ans$个桶的时候可以正确判断出哪一桶是酒 $,$ 所以这个上界也是可以达到的 $.$ 那么我们计算这个式子就可以算出答案了$.$ $O(\frac{p^3}{\ln p}+pq).$ --- [CF547E Mike and Friends](https://www.luogu.com.cn/problem/CF547E) 把询问差分$,$建出$AC$自动机$,$用树状数组维护对答案的贡献$.$ 也可以在广义$SAM$上线段树合并$,$但是很容易$MLE,$需要注意空间常数$.$ --- [CF704B Ant Man](https://www.luogu.com.cn/problem/CF704B) 可以直接$O(n^2)$贪心$,$也可以用堆优化到$O(n\log n).$ --- [CF611H New Year and Forgotten Tree](https://www.luogu.com.cn/problem/CF611H) 枚举$prufer$序列得到关键点的连接方式$,$然后跑网络流$check.$ 记$m=\lfloor \log_{10}n \rfloor \leq 6,$复杂度为 $O(m^{m-2}\times Dinic(m^2,m^2)).$ --- [P6627 [省选联考 2020 B 卷] 幸运数字](https://www.luogu.com.cn/problem/P6627) 随便做$.$ --- [P6628 [省选联考 2020 B 卷] 丁香之路](https://www.luogu.com.cn/problem/P6628) 对于每组询问把编号为奇数的点之间通过一些$(i,i+1)$的边连接起来$,$然后做$mst$即可$.$ $O(n^2).$ --- [CF704C Black Widow](https://www.luogu.com.cn/problem/CF704C) 考虑把布尔表达式当成点$,$在有下标绝对值相同的$x_i$的表达式之间连一条边$.$ 不难发现只会有一些链和环$,$分类讨论$dp$一下就好了$.$ $O(n+m).$ 代码细节很多$.$ --- [CF704D Captain America](https://www.luogu.com.cn/problem/CF704D) 考虑最大化花费较小的那个元素$.$ 建图$,$有源汇上下界最大流$.$ $O(Dinic(n,n)),$网络流图是个二分图$,$所以是$O(n\sqrt n)?$ 两维都要离散化$,$注意细节$.$ --- [CF708D Incorrect Flow](https://www.luogu.com.cn/problem/CF708D) 对每条边$(x,y)$分别考虑$.$ $1.$ $f\leq c:$ $(x,y,c-f,1)$ $(y,x,f,1)$ $(x,y,+\infty,2)$ $2.$ $f>c:$ 先加上$f-c$的花费再加边$:$ $(y,x,f-c,0)$ $(y,x,c,1)$ $(x,y,+\infty,2)$ 然后考虑本来的流量$f:$加入上下界$,$连上上界$=$下界$=f,$费用为$0$的边 然后跑上下界最小费用流即可$.$ $O(Zkw(n,n+m))$ --- [P4094 [HEOI2016/TJOI2016]字符串](https://www.luogu.com.cn/problem/P4094) 建出$SA,$然后考虑二分答案后用主席树$check.$ 时间$O(n\log^2 n),$空间$O(n\log n)$ 如果离线可以做到时间$O((n+m)\log n),$空间$O(n+m)$ --- [P3987 我永远喜欢珂朵莉~](https://www.luogu.com.cn/problem/P3987) [P5610 [Ynoi2013]大学](https://www.luogu.com.cn/problem/P5610) 用并查集维护可能要$/x$的数字的下标$,$每次修改先二分一下然后在并查集上往后跳$.$ 每个$a_i$的变化次数为$O(\log a_i)$次$.$ 每次$a_i$的值发生变化的时候在$BIT$上修改即可$.$ $O(nd\alpha(n)+n\log n\log a_i).$ --- [CF679E Bear and Bad Powers of 42](https://www.luogu.com.cn/problem/CF679E) 势能线段树$.$ 考虑维护每个数字到下一个$42$的次幂的距离$,$修改的时候如果这个距离被减成了负数就递归下去$,$就好了$.$ $O(nlogn\times T),$其中$T$值域内的$42$的次幂的个数$,$为$11.$ --- [CF626G Raffles](https://www.luogu.com.cn/problem/CF626G) 经典贪心题$.$ 对每个点记一下他$+1$和$-1$对答案造成的影响$,$每次修改之后计算一下彩票位置的变化即可$.$ $O(n\log n).$ --- [CF578E Walking!](https://www.luogu.com.cn/problem/CF578E) 题目相当于找若干个子序列形如```LRLRLR...```或者```RLRLRL...```然后把它们拼起来$.$ 我们把分出的子序列分为四类$:$ ```LR,RL,LL,RR.``` 如果有形如```LL```或者```RR```必然有解$.$ 否则如果只有一种```RL/LR```可以直接输出$,$在同时有```RL,LR```的情况下可以用一对```RL``` ```LR``` 拼出一个 ```LL``` 和一个 ```RR``` $O(n).$ --- [CF643D Bearish Fanpages](https://www.luogu.com.cn/problem/CF643D) 在每个点$x$上记除了$f_x$之外$a_x$的权值$,$并把这个扔到$f[i]$的$multiset$里$,$然后模拟就可以了$.$ $O((n+q)\log n)$ 虽然说起来很简单但是细节特别多$.$ --- [CF578F Mirror Box](https://www.luogu.com.cn/problem/CF578F) 不难发现题目要求等价于给黑白染色后的图连出黑色生成树$/$白色生成树$.$ $dfs$缩一下点$,$跑$Matrix-Tree$即可$.$ $O(nm\alpha+k^3).$ --- [CF671D Roads in Yusland](https://www.luogu.com.cn/problem/CF671D) 一种做法是$dp,$用堆维护对答案的贡献$.$ 另一种做法比较有趣$.$[线性规划的对偶](https://www.cnblogs.com/xzyxzy/p/10478865.html) 我们需要知道这个式子 $:$ $max\{ c^Tx|Ax\leq b \}$ $=$ $min\{ b^Ty|A^Ty \geq c\}$ 这里$b,c,x,y$都是列向量$,$ $c,x$长度相同 $b,y$长度相同$.$ 然后我们把这个式子套进题目$.$ 题目可以相当于我们选一些$0/1$放到$y$里使得$A^Ty\geq$一个全$1$列向量$c.$ 对偶过去就变成$:$给每条边设置一个权值使得每条链上的权值和$\leq$这条链的权值$.$ 然后用可并堆维护贪心即可$.$ $O(n\log n).$ --- [CF504E Misha and LCP on Tree](https://www.luogu.com.cn/problem/CF504E) 树剖$,$按$dfs$序建$SA,$然后每次询问查$O(\log)$次$lcp$即可$.$ $O((n+m)\log n)$ --- [CF506E Mr. Kitayuta's Gift](https://www.luogu.com.cn/problem/CF506E) 先$O(n^3)dp$出答案的前$7n+10$项$,$然后跑$BM$即可$.$ --- [CF568E Longest Increasing Subsequence](https://www.luogu.com.cn/problem/CF568E) 首先重复填数对答案没有影响$,$所以先忽略这个条件$.$ 记$f_i$为 以i为结尾的LIS的长度$,$ $g_i$ 为以i为结尾的LIS的上一位$.$ 记$Min_x$为 当前长度为$x$的LIS的最小的结尾 $pos_x$当前长度为$x$的LIS的最小的结尾的位置$.$ 这些都可以简单$dp$出来$.$ 然后我们考虑怎么构造方案$.$ 不是$-1$的位置$x$我们可以直接跳到$g_x$ $.$ 如果$x$所在的位置是$-1,$那么我们优先找$a_y ≠ -1 ,$且$a_y<a_x,f_y=$当前的长度$-1,$那么我们就跳到位置$y.$ 否则$,$我们就只能跳到最近的一个$-1$的位置$.$ $O(n\log n+m\log m+(n+m)k)$ --- [CF704E Iron Man](https://www.luogu.com.cn/problem/CF704E) 考虑对每条重链$/$轻边分别做$,$最后答案取个$min$就可以了$.$ 求线段最早相交的时间可以用$set$维护$.$ $O(n\log n\log m).$ --- [AT3858 [AGC020D] Min Max Repetition](https://www.luogu.com.cn/problem/AT3858) 简单构造$.$ 不难证明最小的次数$k=max(\lceil \frac{a}{b+1} \rceil,\lceil \frac{b}{a+1} \rceil),$然后数列一定是形如$AAAABAAAABAAAAB...$然后$BBBABBBBABBBBA...$的形态$,$二分一下分隔点然后对每个位置$O(1)$判断即可$.$ $O(T(\log a+(d-c)))$ --- [AT3859 [AGC020E] Encoding Subsets](https://www.luogu.com.cn/problem/AT3859) 直接记忆化搜索即可$.$可以证明$,$状态总数不会超过$O(2^{\frac{n}{8}}+n^3).$ 复杂度是$O(n^2S)$的$,$其中$S$表示状态数$.$ --- [AT3860 [AGC020F] Arcs on a Circle](https://www.luogu.com.cn/problem/AT3860) 首先破环为链$,$令最长的$l_i$所在的位置为$0.$ 然后对其它的$l_i,$枚举它们位置的小数部分的大小关系$,$然后再$dp$即可$.$ $O((n-1)!\times 2^{n-1} \times (c\times n)^2).$ --- [P5894 [IOI2013]robots 机器人](https://www.luogu.com.cn/problem/P5894) [my solution](https://www.luogu.com.cn/blog/s-r-f/solution-p5894) 首先题意可以转化为$:$每个玩具有两个属性值$x_i,y_i,$弱机器人可以拿掉$x_i<A_i$的玩具$,$小机器人可以拿掉$y_i<B_i$的玩具$.$ 不难想到可以二分答案$.$ 考虑如何$check$是否能在$mid$分钟的时间内拿走所有的玩具$.$ 首先如果只有一维$,$显然可以直接对$x_i$和$A_i$排序然后丢掉多余的机器人$,$直接比大小即可$.$ 那么多加了一维就是对$x$先贪心$,$每次尽量拿走$y$更大的数字即可$.$ 这个贪心很容易用一个堆来实现$.$ $O(n\log ans \log n).$ --- [CF526G Spiders Evil Plan](https://www.luogu.com.cn/problem/CF526G) 首先选$y$条链相当于找$2y$个叶子节点$,$把它们都联通的边集的边权和$.$ 不难发现必然会选到直径的两个端点$,$所以把两个直径拿出来分别建树$.$ 如果没有强制包含$x$的限制$,$那么就可以直接长剖贪心$.$ 但是$x$不一定会在选$2y-1$个叶子节点的方案当中$,$ 那么我们考虑这两种情况$:$ 在$2y-2$的方案上加一条包含$x$的长链$.$ 在$2y-1$的方案上换掉一条长链$,$并加上一条包含$x$的长链$.$ 这个过程可以用树上倍增实现$.$ $O((n+q)\log n).$ --- [CF1043F Make It One](https://www.luogu.com.cn/problem/CF1043F) 不难发现答案$\leq 7.$ 枚举答案$,$容斥$check$就可以了$.$ $O(n\log n\times ans).$ --- [CF241D Numbers](https://www.luogu.com.cn/problem/CF241D) 只保留$a_i\leq 24$的数值$,$然后$O(2^{24})$暴力即可$.$ --- [P4491 [HAOI2018]染色](https://www.luogu.com.cn/problem/P4491) 二项式反演题$.$ $f_n = $ 钦定 $n$ 种颜色满足条件的方案数 $g_n = $ 恰好 $n$ 种颜色满足条件的方案数 我们要求的是$g_{0..n},$但是$g$不容易直接求$,$那么就先求出$f_{0..n}$然后二项式反演即可得到$g.$ 反演的部分可以用$NTT$实现$.$ $O(T\log T),$其中$T=\min(m,\lfloor\frac{n}{S} \rfloor).$ --- [P3943 星空](https://www.luogu.com.cn/problem/P3943) [CF79D Password](https://www.luogu.com.cn/problem/CF79D) 状压$dp.$ 把问题转换为差分序列上的问题$,$然后就可以状压$dp$了$.$ 转移值可以通过$bfs$提前求出$.$ --- [CF809E Surprise me!](https://www.luogu.com.cn/problem/CF809E) 反演题$.$ 记$p_i$为权值为$i$的点是什么$.$ $\large \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}φ(a_ia_j)dis(i,j)$ $\large = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}φ(ij)dis(p_i,p_j) $ $\large = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\frac {\large φ(i)φ(j)\gcd(i,j)}{\large φ(\gcd(i,j))} dis(p_i,p_j)$ $\large = \sum\limits_{d=1}^{n} \frac{\large d}{\large φ(d)} \sum\limits_{i=1}^{\large \lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\large \lfloor \frac{n}{d} \rfloor} φ(id)φ(jd)dis(p_{id},p_{jd})[i\perp j]$ $\large = \sum\limits_{d=1}^{n} \frac{\large d}{\large φ(d)} \sum\limits_{p=1}^{\large \lfloor \frac{n}{d} \rfloor} \mu(p)\sum\limits_{i=1}^{\large \lfloor \frac{n}{dp} \rfloor}\sum\limits_{j=1}^{\large \lfloor \frac{n}{dp} \rfloor} φ(idp)φ(jdp)dis(p_{idp},p_{jdp})$ 令$T=dp,$把$T$提出来$:$ $\large \sum\limits_{T=1}^{n} (\large \sum\limits_{d|n}\frac{\large d}{\large φ(d)} \mu(\large \frac{\large T}{\large d}))\sum\limits_{i=1}^{\large \lfloor \frac{n}{T} \rfloor}\sum\limits_{j=1}^{\large \lfloor \frac{n}{T} \rfloor} φ(iT)φ(jT)dis(p_{iT},p_{jT})$ 枚举$T,$然后建虚树$,$在虚树上求答案即可$.$ $O(n\log n).$ --- [SP22549 DIVFACT4 - Divisors of factorial (extreme)](https://www.luogu.com.cn/problem/SP22549) 对于每组询问$,$小于$\sqrt n$的部分暴力$,$大于$\sqrt n$的部分可以数论分块$.$ 问题变为若干个询问区间质数个数的问题$,$且询问端点$($ 除了其中最多一个 $)$ 都是形如$\lfloor \frac{n}{i} \rfloor$ 的数$,$因此$Min25$筛即可解决$.$ $O(T(\large \sqrt{n}+\frac{n^{\frac{3}{4}}}{\log n}))$ 注意模数很大$,$要使用快速乘$.$ --- [CF666D Chain Reaction](https://www.luogu.com.cn/problem/CF666D) $O(2^4)$枚举每个点的移动方向$.$ 然后分五类讨论即可$($ --- [P3380 【模板】二逼平衡树（树套树）](https://www.luogu.com.cn/problem/P3380) 在值域上建线段树$,$线段树上套平衡树维护每个点所包含值域区间的下标集合$.$ 所有操作的复杂度都是$O(\log^2).$ --- [P4916 [MtOI2018]魔力环](https://www.luogu.com.cn/problem/P4916) 考虑$Brunside$然后计数$.$ 令$F(n,m)$为不考虑环$,$有$n$个黑的$,$ $m$个白的方案数$.$ 令$G(n,m)$为考虑环的方案数$.$ $F(n,m)$可以枚举连续$k+1$个黑色的总数并容斥$,O(\lfloor \large \frac{n}{k+1} \rfloor)$ 计算$.$ $G(n,m)=\sum\limits_{i=0}^k (i+1)F(n-i,m-1).$ 所以$G(n,m)$可以$O(n)$计算$.$ 然后枚举$\gcd (n,m)$的约数并计数即可$.$ 复杂度$O(n\sqrt n)$ --- [CF1149D Abandoning Roads](https://www.luogu.com.cn/problem/CF1149D) 考虑一条路径存在的条件$:$在已经把$A$边形成的联通块合并起来的时候$,$当且仅当路径中的所有$B$边连出了一个环时不合法$,$否则必定合法$.$ 那么很容易有一个$O((n+m)2^n)$的状压$DP.$ 发现大小$\leq3$的联通块是不用记录进状态里的$,$只需要临时判一下就好$.$ 这样联通块个数就变成$\lfloor \frac{n}{4} \rfloor$ 了$.$ $O((n+m)2^{\lfloor \frac{n}{4} \rfloor}.)$ --- [P5279 [ZJOI2019]麻将](https://www.luogu.com.cn/problem/P5279) 考虑建出麻将自动机$,$用$dp_{0/1,0/1/2,0/1/2}$和$cnt$来表示胡牌状态$.$ 搜索一下可以发现自动机里的点数只有$2092$种$.$ 然后$O(n^2\times 2092)$ $DP$一下即可$.$ --- [P4314 CPU监控](https://www.luogu.com.cn/problem/P4314) 区间赋值/区间加/查询区间最大值/查询区间历史最大值$.$ 维护加标记,区间历史最大加标记,赋值标记,历史最大赋值标记即可$.$ 设序列长度为$n,$操作次数为$m,$则复杂度为$O((n+m)\log n).$