1.AppleTrees (SRM489)
考虑对于每一种排列，求出顺次摆放最少的位置。
然后把多余的位置插入在\(n+1\)个空位中即可。
对于前一个问题，可以发现就是每个空位的贡献是 \(max(r_i,r_{i+1})\)。
所以把所有的树按照 \(r_i\) 的大小排序，每次把最大的插入其中，考虑是否连边即可转移。
2.Unscrambling a Messy Bug (IOI2016)
考虑分治，\(solve(S,T)\) 表示由 \(S\) 映射到 \(T\)。
能用到的信息主要是字符串中 \(1\) 的个数。
每次把 \(S\) 折半，然后即可递归两个部分，对于右半部分强行令左半部分的权值为 \(1\) 即可。
当前分治层要求线性于 \(|S|\) 复杂度，但是直接 \(O(1)\) 插入，然后查询是 \(\binom{|S|}{|S|/2}\) 的。
优化方法是对于当前分治层用 \(1\) 的个数为 \(1\) 的字符串统计，对于递归的部分都加上这个东西就行了。
3.Divisible Substring (ABC158 E)
有这样一个事情，对于 \(\gcd(p,10)=1\)，可以将字符串 \(x..y..z\) 看作 \(x..y..z00..00\)。
所以只要特判 \(p=2,p=5\)，对于其他的情况作后缀查哈希表即可。
4.Devu and Locks (Codechef DEVLOCK)
很简单的数位 dp，然后第一眼就是矩阵快速幂优化转移。
但是本题的转移非常简单，\(i,j\) 转移到 \(i+j\)，这是一个卷积形式。
所以应该对特殊形式的递推（类似的还有异或）敏感一些。
然后可以倍增+二维 FFT，似乎因为常数大过不了。
可以这样去做，把 \(10^i \pmod p\) 的每个取值个数找出来，然后对于每个取值分别做一下倍增。
最后再用二维 FFT 合并到一起就好了。
5.Glamour
状压出现次数 \(\bmod 3\) 的结果，然后记录一下当前权值 \(\bmod k\) 的结果。
然后直接用上一道题的第一个方法搞，但是这里的维度达到 \(7\) 维。
但是每个维度都是对 \(3\) 做循环卷积，所以可以想到用单位根优化这个东西。
然而 \(\bmod 998244353\) 意义下不存在三次单位根，所以根据 \(1+w_3^1+w_3^2=0\) 这个式子，压一个结构体表示 \((a+bw_3^1)\)即可。
口胡了一个做法大概是，枚举 \(3^{|S|}\) 表示对 \(|S|\) 个维度的变量分别代入 \(w_3\) 的多少次方，然后可以求得一个多项式。
对多项式的每一项中的 \(3^{|S|}\) 个点值插值回去。
6.\(n\) 个点 \(m\) 条边的带标号无向图。
暴力就是枚举第一个点所在连通块然后直接合并。
然后正解的做法就是用一下斯特林反演，把问题转化为计数形成了至少 \(i\) 个连通块。
假设最终有 \(k\) 个连通块，那他被计算的次数就是 \(s2(k,i)\)，给这个东西乘上 \(s1(i,1)!(-1)^i\) 的系数累加起来就是答案。
其实 \(s1(i,1)=(i-1)!\)，考虑通过转移的顺序来计数这个 \((i-1)!\)，那其实就是只有最后一次钦定 \(1\) 号点所在连通块必须在内。
7.Gxor (SRM 670)
贝尔数枚举集合划分，然后计算方案数乘上对应系数即可。
方案数是要求一些异或方程满足，这个直接高斯消元即可。
8.独立集、团通信问题
考虑 \(A\) 集合（团）中是否存在度数 \(\leq \frac{|A|}{2}\) 的点 \(x\)， \(B\) 集合中是否存在度数 \(> \frac{|B|}{2}\) 的点 \(y\)。
如果 \(x,y\) 均不存在，那么 \(A,B\) 显然无交。
否则可以根据 \(x,y\) 将集合缩小一下就好了。
9.投影对称
如果有了对称点两两匹配的方案，那么只要判断每个中点是不是在同一条直线上。
因为两点确定一条直线，所以暴力做法可以直接枚举两个中点。
然后正解是这样的，可以先确定出重心来，然后这条中点的直线一定得过重心，所以可以把重心当做确定直线的一个点。
10.Future of draughts
预处理出所有答案，然后考虑首先忽略每一步非空的限制，要求的其实是 \(\prod \limits_{i=l}^rtr((A_i+I)^k)\)。
这里的 \(A\) 为邻接矩阵，\(I\) 为单位矩阵，\(tr(A)\) 表示 \(A\) 的主对角线的和。
对于每一步非空的方案数，可以进行二项式反演求得。
然后对于 \(tr(A^k)\)，求法是这样的。
有这样一些事情：
考虑求出 \(C(x)\) 为 \(A\) 的特征多项式，那么 \(C(A)=0\)。
所以把 \(tr(A^i)\) \(i \in [1,2n]\) 全求出来高斯消元即可解出特征多项式。
然后用这个式子线性递推出每一项就好了。
11.经典问题2
大概的思想就是求代数余子式矩阵。
然后结论是 \(AA*=|A|I\)，其中 \(A*\) 为伴随矩阵即代数余子式矩阵的转置矩阵，\(|A|\) 为 \(A\) 的行列式。
然后用拉普拉斯展开即可解决这道题。
12.常系数线性递推
这个玩意的转移矩阵称为 \(Frobenius\) 矩阵，特征多项式为 \(C(x)=x^k - \sum \limits_{i=1}^k c_ix^{k-i}\)。
要求的东西形如 \((A^{n-1}B)_{1,1}\)。
令 \(A^{n-1}=C(A)D(A)+R(A)\)，因为 \(C(A)=0\)，所以有 \(A^{n-1}=R(A)\)。
所以 \(b_n=(A^{n-1}B)_{1,1}=\sum \limits_{i=0}^{k-1}r_i * (A^i*B)_{1,1}=\sum \limits_{i=0}^{k-1}r_i*f_{i+1}\)。
只需要求出 \(A^{n-1}\bmod C(A)\)，这个玩意用倍增就可以实现了。
13.Teams IOI2015P3
贪心的做法比较简单。
然后考虑把每个区间 \([l,r]\) 都表示为二维数点 \((l,r)\)。
观察可知已经失效的集合为一些 \(y\) 随 \(x\) 递减的矩形的并。
所以不断取最小就是不断取最靠后的矩形并尝试与前面较高的矩形合并。
14.Evaluate the polynomial
多点求值，但是模数比较特殊。
做 \(\bmod x^{2^18}\) 的 \(NTT\)，代入的就是每个 \(g^{3i}\)，这样就发现已经能回答三分之一的询问了。
对于 \(g^{3i+1},g^{3i+2}\)，化一下式子也可以解决。
15.Sorting IOI2015P5
答案是可以二分的，原因是可以重复熊孩子的操作使得情况不劣。
然后操作是可以交换的，原因是可以构造出交换之后等价的方案。
所以先让熊孩子操作完，然后通过排列的环的个数即可算出要进行的操作次数。
对于输出方案构造一下交换即可，对于在线用平衡树支持区间的合并分裂操作来维护环即可。
16.星空
首先权值是循环卷积，然后模数 \(998244353\) 存在 \(\bmod 17\) 意义下的单位根。
所以可以对每个单位根直接代入点值计算结果，然后最后暴力 \(IDFT\) 回来。
暴力做法是用总方案数 - 不连通方案数。
前者可以直接背包，后者枚举 \(1\) 号点所在连通块即可，复杂度是 \(O(p3^n)\) 的。
这个玩意在整数上的计数方法一般都可以用 \(EGF\) 然后搞一搞 \(ln,exp\) 啥的。
大概就是联通方案 \(F\) 可以通过相互无影响的卷积来构成不连通方案 \(G\)，所以 \(G(x)=e^{F(x)},F(x)=ln(G(x))\)。
可以理解在集合意义上这也是正确的，只要把卷积改成集合的不交并卷积。
把 \(F,G\) 的每一位上都视为有一个占位多项式表示 \(size\) 大小为 \(i\) 的系数，然后对这个玩意进行一下 \(FMT\)。
之后的乘法操作是对位多项式卷积，加法操作是对位多项式对位相加。
然后可以理解对 \(G\) 取 \(ln\) 实际上就是对每个占位多项式分别取 \(ln\)，因为不同多项式之间是无影响的。
然后 \(IFMT\) 回去这题就做完了。
另一个做法是用斯特林反演。答案要求恰好一个连通块，就枚举强制不联通的连通块的划分，然后乘上两类斯特林数即可。
对于容斥中的阶乘系数，仍然是考虑枚举 \(1\) 所在连通块来去一个阶乘，剩下的按照任意顺序选择。
可以发现要求的东西形如 \(f*\sum \limits_{i=0}^{\infty}g^i=f*\frac{1}{1-g}\)。
所以用和上一个做法一样的方式来对每个占位多项式求逆就好了。
京公网安备 11010502036488号