耳分解

qoj3301，正如算法名称，像耳朵一样分解，一个强连通分量是通过一个更小的强连通分量加入一条链形成的，反之，强连通分量也可以通过次缩成一个环，点双也相同。此题直接dp，\(f_s\)表示s集合构成强连通分量的代价，考虑枚举一条链，\(g_{s,u,v}\)表示目前所有探测到的点集合为s，目前如果将u和v连接群里就可以形成强连通分量的代价。做完了

p5776，点双版本

数据结构

p8264，首先考虑n方暴力，直接模拟即可，如何快速进行这个东西，假设我们可以预处理出每个区间进入的值和对应的值的映射，就可以O(1)做，平衡一下复杂度，考虑分块，这样一个询问是根号的，那么如何预处理呢，把映射看成函数的话，一个变换相当于整体向下移动，然后把负坐标的翻转，那么此时翻转的和某些没翻转的一样，并且没翻转的是一个区间。那就好做了，把前面的操作看做一个线，线表示目前的0，记录l，r表示目前没有被替代的区间，就可以做了

线段树处理某些经过区间，或者区间前缀后缀的问题，或者区间限制，考虑线段树单侧递归

p8518，先操作差分，以q为下标建线段树。考虑没有上界的限制咋做，我们找到最小的最右边的位置，如果小于0则以它为0，算后缀和即可。我们发现答案只和最后一次碰壁有关，而且如果极差大于c则一定碰壁，直接二分即可，细节较多

凸性(slope trick)

p3642，把dp看成点值函数，先考虑叶子节点的答案，只有(0,0)，考虑叶子节点对父亲的贡献，发现是个类似v字图的东西，叶子合并上去相当于加上这个图像。考虑一般情况，即节点对父亲的贡献，记L,R为斜率为0的那一段的左右端点，len为边的长度。\(x\le L\)的地方斜率肯定\(\leq-1\)所以直接让len=0，\(L\le x\le L+len\)的地方让他到\(L\)，\(L+len\leq x\leq R+len\)的地方不用变，\(R+len\leq x\)的地方让他到\(R\)。转化到图上就是最右边一段斜率全变1，权值为0的一段向右平移，再左边一段插一个-1斜率的线，再左边集体抬高len，slope trick轻松做完

数学

p3543，如果没有区间操作相当于直接exgcd，然后分类讨论最优。区间操作我们考虑差分一下，那么就是前面-a，后面+a状物，其实就是配对，最后要求全变0，我们考虑先每个都按自己取最优，然后可能不满足\(\sum{x}==0 (x=count(a))\)我们考虑调整，反悔贪心即可

cf906d，再次看这个题，发现很多地方不懂，要严格遵循欧拉公式，不要在<mod的时候还去加mod，ksm里也要遵循欧拉公式

p7325，首先有两个结论，设\(f_i\)为正常的fib序列，\(F_i\)为特殊的，那么\(F_i=bf_i+af_{i-1}\)数学归纳一下就行，然后fib循环节模m最长不超过6m。如果m和某些东西互质，那么就做完了。考虑a，b，m先都除掉gcd，然后如果我们知道gcd(a,m),gcd(b,m)就很好做，发现\(f_n\)和\(f_{n-1}\)互质，然后发现gcd(a,m)是\(f_n\)的因数也就是是gcd(\(f_n\),m)的因数，发现gcd(\(f_n\),m)是a的因数也就是是gcd(a,m)的因数，这两个gcd想到，b也同理，所以我们仍然可以查表。

构造

qoj1840，首先如果数列长度没限制可以这么填，-1，1，1...但是有限制，我们考虑如果先随便填一些小数，或者0，可以堆到很高的一个势能（暂时叫这个），值为x的方案数有这样一个性质，x越大方案数越小，所以我们瞎填一些小数，然后从小到大去贪心的填剩下的，感觉正确率很高，用while（1）保证一定正确，否则超时

长链剖分

uoj84，一种链剖分技巧。性质1，如果dfs每次遍历整个次大长链，总的复杂度是O（n）的。性质2，跳链跳根号次就能到根，这个题考虑其实是一个点不瞬移的，主体肯定到某个点停一下，那么我们枚举下一个停的点即可，长剖优化可到O（n）

串串

p6793，考虑SA，如果能够建出后缀树，那么按LCA从深到浅匹配最好，对应到SA上就是height数组从大到小，用并查集

计数中乘法等于卷积，容斥系数和方案数的乘积

p10104，花了我5天时间，单独开一篇不为过，首先m=0的话就是从高位到低位枚举，全填的话是子问题，考虑不全填怎么计数，枚举最长的全填序列，然后下一位填自由元，两个变量表示与全填的奇偶性，可以递推。接下来考虑原问题，我们一个显然的想法是容斥，边集容斥，然后发现其实有用的只有连通块怎么划分，考虑算一个连通块的容斥系数（类似于-1的几次方的和），一个方案就是所有连通块容斥系数之和，假设我们知道了连通块的容斥系数之和怎么做。考虑记录连通块的有贡献的那个点的集合和连通块们占领的集合，每次枚举一个连通块转移，发现复杂度很爆炸。发现如果a是从小到大的话，可以枚举i表示mask中<=i的位表示贡献点，>i的表示占领点，容易转移。那么接下来就是如何求连通块系数。我们的系数是关于连通块联通的一些东西，那么可以考虑随便选-一定不连通的，做完了

agc041_f，花了也将近5天，首先考虑容斥有多少点不被覆盖，称其为关键点，集合容斥是简单的，然后发现每个关键点相同的列没车，我们考虑枚举关键点列集合，去dp容斥系数和方案数乘积的和（把这个东西叫做val），那么我们只需要考虑这一行放几个关键点，如果不放对val的贡献是\((-1)^{0}*2^{len-s}\)，放x个的话方案数是1，其实就是容斥系数之和，是-1（如果集合大小大于0的话，否则是0），然后这样的话无法确定集合内的每一列都是有关键点的，所以考虑再容斥，枚举一定没有关键点的（称其集合T），减去就行，这样的话发现如果t=s那么贡献是0，否则有-1的贡献，分两个数组记录s是否等于t，然后笛卡尔树上dp就行

dp

loj6069，可以不用立即算出某些东西，把他当成一个势能（系数）放在一维状态里，用到的时候可以立取

cf1603，发现排好序一定不影响，然后变成选区间，然后变成选前缀，然后暴力dp，n6方，考虑优化，枚举最小值可以根号，总和的一维可以减去最小值和个数的乘积，做完了

势能dp，用到的时候再算

at_wtf19_b，就差一点吧也许，最重要的一点，将区间转换成单点，定义\(s_i\)为前缀和\(mod 9\)，那么相当于\(s_{l-1}=s_r\)发现可以给编号，离散化后，编号相同的方案数是不同的方案数+1，可以轻松算出，然后枚举新编号集合直接状压，ans算答案一开始直接算好，dp数组算系数。

计数

arc154_e，神奇题，首先考虑对于一个固定的p怎么做，树状数组？有更简单的做法，考虑算i的系数，那么就是i为r的时候+，否则-，那么其实就是下标小于i的个数减去值域小于pi的个数，然后化一下式子就是i方减去 i乘pi，考虑算pi的期望位置，然后最终乘总数就是和，发现被操作过的话，期望位置就是\(\frac{n+1}{2}\)概率是好算的。

agc056_b，首先考虑对xi计数，发现不好弄，考虑对pi计数，发现会重，考虑放最前面，区间dp即可

p10103，从n-m个人选m个人到前m个位置，再乘fac，然后后面的有n-2m个受限制的，m个自由的，考虑递推。设\(f(n,m)\)表示n个受限，m个自由，一个自由的可以待在自己位置，或者去别人位置（等于一个受限的），发现是两个加起来，类似组合数。一个受限的可以去自由的位置，或者传统错排，做完了，考虑分块

贪心

p9600，首先ci要么x能到要么y能到要么是0，那么其实就是
CF436E Cardboard Box，只不过要保证连通性，那么分类讨论一下，更好的不用堆的cbox做法是，先考虑选两个的，然后如果选一个的选两个比这个优肯定选一个（集合名字）的一个，就没了

p8860，首先如果我们让每个边的边权等于第一次被访问的时间，则边权两两不相同，此时我们要求出那个排完序后字典序最大的路径留下，可以主席树+dij，但是也可以贪心，贪心就直接看dij的堆谁先扩展，这个是对的，可以考虑证明

字符串

arc151e，分类讨论，如果有公共子串就直接输出一个可得到的答案，否则最短路求多少步得到公共子串，求公共子串可以hash

组合意义

p4921，首先考虑钦定k个配对的，选k个座椅，选k对情侣，情侣的位置2的k次方，情侣座位顺序fac[k]，那么剩下的都不配对，考虑递推，容易发现是简单的