奥术神杖（分数规划、AC自动机）
发现我们要求的东西很像一个平均数（实际上就是几何平均数），那么我们现在考虑一种运算，使得乘法能够变成加法、开根可以变成除法，不难想到取对数满足这个条件。我们对(sqrt[v]{prod a_i})取(ln)之后得到(frac{1}{v} sum ln a_i)，那么我们现在需要它最大。
这显然是一个分数规划，二分之后考虑check。发现check类似于字符串匹配，在AC自动机上DP求解即可。复杂度(O(nslogfrac{ln 10^9}{eps}))
注意一个细节。输出方案的时候可能存在：模板串当前位置为'.'时有多种方案满足最优解，但是当前位置字符确定。在输出的时候需要额外的判断。
勘破神机（递推、二项式定理）
强行二合一最为致命……
(f_i)是(f_0 = f_1 = 1)的斐波那契数列，设(g_i)表示(3 imes 2i)的棋盘的方案数，可以得到(g_i)的递推式为(g_i = 2sumlimits_{j=0}^{i-1} g_j + g_{i-1})，即(g_i = 4g_{i-1} - g_{i-2},g_0 = 1 , g_1 = 3)。
(f_i)的通项公式为(frac{1}{sqrt{5}} ((frac{1 + sqrt{5}}{2})^{i+1} - (frac{1 - sqrt{5}}{2})^{i+1}))，(g_i)大力解一下特征方程或者丢到OEIS上找一下可以得到通项公式(g_i = frac{sqrt{3}}{6} ((1 + sqrt{3})(2 + sqrt{3}) ^ i - (1 - sqrt{3})(2 - sqrt{3})^i))。
然后因为(inom{x}{k} = frac{x^{underline{k}}}{k!})是一个多项式，把多项式的系数求出来问题就等价于求(sumlimits_{i=l}^r f_i^k)和(sumlimits_{i=l}^r g_i^k)，方法跟这里的一样。
Upd：上面的链接挂掉了QAQ来更个新
先可以变为求(sumlimits_{i=1}^l f_i^k)，然后把通项公式代入并用二项式定理拆开，答案就是(frac{1}{sqrt{5}^k}sumlimits_{j=0}^k (-1)^j inom{k}{j} sumlimits_{i=1}^l (frac{1 + sqrt{5}}{2})^{(i+1)(k-j)}(frac{1 - sqrt{5}}{2})^{(i+1)j})，最后一个(sum)显然是等比数列求和的形式。快速幂/分治计算均可。
然后注意模数比较鬼畜、没有二次剩余的话可以扩域，即把所有数表示为(a+bsqrt{5})的形式。
关于特征方程一篇还不错的Blog
送别（？？？）
不会留坑
排兵布阵（背包）
BJOI出PJ题……
考虑暴力DP：设(f_{i,j})表示考虑前(i)个城市共用(j)个士兵的最大分数，然后不难发现每一个城市中的驻扎人数在恰好为(2x+1)时才有可能达到最优，其中(x)是第(i)个城市的其中一个人的驻扎兵力，那么有效的驻扎兵力数只有(S)个，(O(NMS))地DP即可。
光线（？？？）
考虑将两个玻璃合并。那么枚举在两块玻璃之间反射了多少次，就是一个无穷等比数列求和。
不难得到光线从((a_i , b_i))和((a_j , b_j)(j=i+1))两块玻璃之间穿过的概率是(a_ia_j frac{1}{1-b_ib_j})，从(j)层穿入、再从(j)层穿出或者从(j)层反射的概率是(b_j + a_j^2b_i frac{1}{1-b_ib_j})，这就是将两个玻璃合并之后从下表面反射的概率，从上表面反射的概率同理。那么我们就可以把两个玻璃合并起来。从上往下依次合并，就可以避免记录从上表面反射的概率。
删数（线段树）
一个很巧妙的转化：考虑序列中的一个数(x(x leq N))如果它出现了(p)次，则覆盖区间([x-p+1,x])，那么答案相当于求([1,N])内没有被覆盖的整点个数。
那么我们需要动态维护这个东西，支持单点修改、区间平移，直接用线段树维护。值得注意的一点是：当(x>N)的时候不能够产生贡献，区间平移的时候需要注意这一点。