ARC143D
非正解：
考虑将 x 分为两部分，不妨设 \(x = 10^7A+B,A\in[0,10^2),B\in[0,10^7)\)，而 A,B 对于答案的贡献也可以分开成两半，两半之间贡献只有 B 可能对 A 产生最低位的进位，对于所有 B 预处理出贡献，这一部分可以 \(O(B)\) 完成，而对于 A 的部分，不妨枚举所有可能的 A，并枚举哪一些数是从 B 获得了进位，即可在 \(O(AN)\) 里计算答案，最终复杂度为 \(O(B+An)\)，AB 的取值范围是由最后的复杂度计算得到，对于任意的 \(n\) 和值域 \(Max\)，该做法可以得到复杂度 \(O(n\sqrt {Max})\)，由于值域较小可以过
正解：
对于序列 \(a_n\) 按照 \(a_{i}\mod 10^k\) 的升序排序，进位是由结尾开始连续的一段，所以对于每一个 \(k\)，一共可能的位置只有 \(n + 1\) 个，于是可能的状态只有 \(k(n+1)\) 种，逐层进行 DP 可得到答案
CF1782F
将 ( 看作 1，) 看作 -1，那么每次插入的部分和都为 0，合法的条件为任意前缀和大于等于 0。
考虑DP，\(f_{n,t}\) 为 n 次操作后，任意前缀和大于等于 t，考虑将问题转化为子问题，可以枚举与第一个字符同时加的字符的位置，不妨设两者之间有 2k 个字符，由于与第一个字符同时加入的字符的位置与每次加入的是 () 还是 () 无关，那么有转移 \[ f_{n,t} = \sum g_{n,k}(pf_{k,t-1} + (1-p)f_{k,t+1})f_{n-k-1,t} \] 其中 \(g_{n,k}\) 为 n 次插入，第一个字符与他对应的字符减恰有 2k 个字符的概率，可以通过 DP 求出，后面相乘的两者为被这一对字符分割出来的两个互不干扰的子问题，最后答案就是 \(f_{n,0}\)。
ICPC2022 Nanjing J
限制等价于 \(a_i + i\) 或 \(a_i - i\) 相等。对于对应的两种数值建成二分图的点，原来的数字为边，那么就转化为了将二分图划分为若干长为 2 的链，显然连通块有奇数条边时不行，而有偶数时随便去都能取出符合条件的。
ICPC2022 Nanjing F
对于一棵树，其满足条件的概率为 \(\prod\frac{1}{sz_i}\)，而添加了 NaN 之后的答案就是，被 NaN 分开的多个子树的概率直接，不妨枚举 NaN 所在的位置，容易发现本质不同的位置数量只有 \(O(\log^2n)\) 种，枚举这些本质不同的位置，计算其概率和可能数量然后相加，对每一种位置这一部分可以 \(O(\log n)\) 计算，所以一共可以在 \(O(\log^3n)\) 解决一次询问
UOJ782
先找出最开始的最大后缀，然后再这基础上讨论加，手玩一下容易发现与 border 有关，只有是 border 的时候后缀有可能更大。令 \(T = g(S)\)，那么 \(g(ST)=RT\) 而要满足 \(RT\) 比 \(T\) 大当且仅当 \(R\) 为一个 border 。而且对于不同的 border 形式比较一下，发现 \(R\) 是最小 border 重复时得到的答案比最小 border 的优，否则更劣，所以 \(R\) 为最长的最小 border 的重复，然后分 \(R=T\) 和 \(R\neq T\) 时可以快速得到每一次的 \(g(f^k(S))\)。
UOJ 792
考虑子序列求解方法有 \(f_i = 2f_{i -1}-f_{last_c - 1}\)，在模 2 意义下有 \(f_i = f_{last_c - 1}\)。在树上，边上有字符的情况下，这是一次跳点，即 \(i\rightarrow last_c-1\rightarrow last'-1\) 变为了 \(x\rightarrow y\rightarrow z\)，这个减一因为边和点的关系不存在了， 就可以变成一个点的等价类的关系，等价类中的所有点都两两合法，直接把点归到等价类中深度最小的那个，然后计数就可以。