有几个理论/技巧。
高维卷积
仿照一维 DFT 的形式，我们有如下过程：依次考虑每一维，假设现在考虑到第 \(i\) 维，则对其按照其余的维度分类，每一类中恰好有 \(d_i\) 个数，然后对这 \(d_i\) 个数进行 DFT，然后就可以得到点值，点值相乘之后 IDFT 也是类似操作。
短多项式幂
设短多项式 \(F(x)\) 的度数为 \(d=O(1)\)，现在要求其 \(k\) 次幂 \(\bmod x^n\) 的值。
首先需要保证 \(F(x)[x^0]\) 的值不为 \(0\)，如果为 \(0\) 可以提出来单独计算，然后计算出 \(F^k(x)[x^0]\) 的值。
设 \(G(x)=F^k(x)\)，对两边求导，有
将其配凑一下，变成
考虑其第 \(n\) 位的系数，有
将左边的 \(G'(x)\) 写成 \(G\) 的形式，就有
这样我们有 \(G(x)[x^{n+1}]\) 与前几项的关系，就可以 \(O(nd)\) 递推了。
[CF1329I Kevin and Grid](Kevin and Grid)
首先有平面图欧拉公式：\(C=|E|-|V|+|F|-1\)，其中 \(C\) 是联通块个数，\(E\) 是点集，\(V\) 是边集，\(F\) 是划分出的区域集合，相当于环。
我们考虑直接利用这个公式来做，我们要求的答案就是 \((|E_1|-|V_1|+|F_1|+|I_1|)-(|E_2|-|V_2|+|F_2|+|I_2|)\)，其中 \(I\) 表示不和边界联通的联通块集合。
我们考虑 \(|F_1|-|I_2|\) 是什么，对于 \(F\) 中的每个非四元环，其一定恰好对应一个对面颜色的联通块，因此这个式子减出来就是四元环个数。
因此我们只需要计算在每个 \(x\) 下的点数，边数，四元环个数即可，容易用 FFT 实现，时间复杂度 \(O(V\log V)\)。
CF1085G Beautiful Matrix
首先我们需要求出 \(f_i\) 表示长度为 \(i\) 的排列，满足对于所有 \(j\)，\(p_j\not=j\) 的个数。为了解决这个问题，我们设 \(dp_{i,j}\) 表示长度为 \(i\) 的排列，前 \(j\) 个受到 \(p_j\not =j\) 的限制。若 \(j=0\) 则方案数为 \(i!\)，否则考虑第一个受到限制的位置，考虑其填的是受限制的还是后面不受限制的，就可以转移了。
错排还有 \(O(n)\) 的递推，但是因为我们后面还要用这个 \(dp\) 数组，所以我们先这样 \(O(n^2)\) DP 了。
然后我们考虑确定第一行的一段前缀，后面任意的方案数，这个直接模仿康拓展开算就行。
然后从第二行开始，不仅要满足小于前面的排列的限制，还要满足错排的限制，这个可以直接用前面的 DP 数组中的值来算，然后就做完了。
因为需要一个康托展开类似物，所以是 \(O(n^2\log n)\) 的。
[2021 集训队互测] 愚蠢的在线法官
首先根据行列式的一些基本性质，如果 \(A_i\) 有相同的，也即两行相同，则行列式为 \(0\)。
然后，我们发现，如果交换相邻两个 \(A_i\)，则行列式的值不会变，因为会同时乘上两个 \(-1\)，因此 \(A\) 的顺序对答案是没有影响的。
考虑在树上解决这个问题。我们设 \(dp_{i,j}\) 表示在 \(i\) 的子树内，有 \(j\) 个点还没匹配的系数和。转移容易做到 \(O(n^3)\) 或者 \(O(n^2)\)。
最后，我们发现，如果有若干个点 \(i\) 子树内的点匹配了 \(i\) 子树外的点，则这些点可以看做是相同的。而 \(\geq 2\) 个相同的对应的答案是 \(0\)，因此只有 \(j\in[0,1]\) 是有用的。同时合并子树的时候也只有 \(0,1\) 是有用的，因此可以做到 \(O(n)\)。
飞翔的胖鸟
原题我也不知道在哪里。
设角度为 \(\theta\)，则花费的体力值是 \(b\theta+\frac{ah}{\sin \theta}\)。
对其求导，其导数为 \(b-\frac{ah\cos \theta}{\sin^2\theta}\)，令其 \(=0\)，移项有 \(\frac{b}{ah}=\frac{\cos \theta}{\sin^2\theta}\)。
设 \(k=\frac{b}{ah}\)，特判其为 \(0\) 的情况，然后假设其不为 \(0\)，可以解得 \(\cos \theta=\frac{-1+\sqrt{1+4k^2}}{2k}\)，然后算出 \(\theta\) 即可，容易验证其在 \((0,\frac{\pi}{2}]\) 内。
Prefix Sum
考虑第 \(i\) 个位置对 \(j\) 位置前缀和的贡献，是 \(i-j+k-1\choose k-1\)。
则将其拆成 \(a_{x,y}x^iy^j\) 的形式，然后用树状数组维护 \(x_i\) 即可。
时间复杂度 \(O(nk\log n+nk^2)\)。
[集训队作业2018] 复读机 加强版
\(d=1\) 显然是 \(k^n\)。
\(d=2\) 考虑单位根反演，相当于给每个人随机赋值 \(1\) 和 \(-1\)，然后每个人出来复读会产生其权值的贡献，总权值是所有人的权值之积。那么我们枚举多少人给 \(1\)，多少人给 \(-1\) 就可以做到 \(O(k\log n)\)。
\(d=3\) 仍然按照上面的做法可以做到 \(O(k^2\log n)\)。\(19491001\) 的原根是 \(7\)。
\(d=4\) 以上就不能暴力枚举了。但是发现，\(d=4\) 实际上只要算选了几个 \(1\) 和几个 \(\omega_{4}^{1}\) 即可，这里可以是负的，但是弄个偏移量就可以弄成正的了。
这个题就转化成有一个二元生成函数 \(F(x,y)\)，其次数可以看做常数，在这里是 \(d=2\)。然后我们要求 \(F^k(x,y)\)。
模数并不能让我们高维卷积，所以只能考虑短多项式幂了。二维情况的短多项式幂和一维类似，把求导换成求关于任何一维的偏导即可。复杂度 \(O(k^2d^2+k^2\log n)\)。
对于 \(k=6\) 我们发现上面的方法好像又不行了，因为这样有三个维度。但是实际上 \(\omega_{6}^{1}=1+\omega_{6}^{2}\)，所以还是只需要两个维度的，然后就做完了。
进一步的，如果是 \(d\) 阶单位根，只需要 \(\varphi(d)\) 个单位根就可以线性表示出所有元素了。但是我并不会证明这个结论。
[2021 集训队互测] 抽奖机
考虑单位根反演，给每个位置赋 \(1,\omega_3^1,\omega_3^2\) 的权值。设第 \(i\) 个位置最后被转了 \(a_i\) 次，赋的值是 \(b_i\)，要求是 \(c_i\) 则贡献为 \(\prod\limits_{i=1}^{n}b_i^{a_i-c_i}\)。
这样子每次操作贡献就是独立的，可以直接快速幂计算。我们现在需要计算两个东西：每种分配方案与操作之间的系数，以及每种分配方案与最终的系数关系。
我们先来考虑第一个，考虑枚举分配了几个 \(\omega_{3}^{2}\)，然后再枚举分配了几个 \(\omega_{3}^{1}\)，就可以写出一个 DP：设 \(dp_{i,x,y}\) 表示分配到第 \(i\) 个，操作中还有 \(x\) 个 \(1\) 旋转与 \(y\) 个二旋转没有分配的方案数。DP 转移一次是 \(O(n^2)\) 的，总共需要转移 \(O(n^2)\) 次，总复杂度是 \(O(n^4)\) 的。
对求出来的值快速幂之后需要将其转化回去。我们会发现这东西其实是和上面的 DP 差不多的，改一改单位根即可。于是这题就可以做到总复杂度 \(O(n^4+n^2\log k)\)。
另外上面这个过程也可以看做对其做 \(3\) 进制 FWT，因为 \(1\) 的个数和 \(2\) 的个数一样的可以放在一起做，所以总共只有 \(O(n^2)\) 个状态，将其转化成点值之后转化回来的过程。