Poly技术合集

1、四则运算

基础中的基础

2、牛迭技术

\(G_1(x) = G_0-\frac{F(G_0(x)}{F'(G_0(x))}\)

如果偶遇阴间题，两个poly相互迭代，请使用拆高低位暴力解方程。因为poly题正确性永远是第一位，不熟悉的调不出来别来问我。

3、整体思想

1、\(F(ax)\)，如果遇见 q-多项式 形式的东西，请使用这个。

2、\(F(wx)\)，在 LSB 中有涉及。

3、\(F(x^a)\)，在欧拉变换中有所涉及，如果问题涉及群结构，这个变换是常用的。

4、\(F(G(x))\) 常在拉反中出现。请务必保证，G(0)=0

5、EGF/OGF 在计算过程中的转变。这个是 Poly 刻画不出来，但代码能刻画的。有些 Poly 难，就是因为中途反复的需要调整思路角度。

4、反演思想

1、容斥。
烂大街的容斥就不讲了，讲讲做题技巧和Poly推导。

容斥可以用 Poly 刻画，但是有容斥的 Poly 难度较高的原因在于，容斥需要构造一个组合对象。

公式1：\(f_i = \sum_{j=0}^{i} \binom{i}{j} g_j\)

做法：此时对于 \(F,G\) 的 EGF，我们显然有 \(F(x) = e^x G(x)\)，所以有 \(G(x) = e^{-x}F(x)\)，反演公式显然，而且是 \(O(nlogn)\) 的。

公式2：\(f_i = \sum_{j=i}^{n} \binom{j}{i} g_j\)

做法：我们反向设 \(EGF\) ，即 \(F(x) = i!f_i x^i\)，此时有 \(F(x) = e^{\frac{1}{x}}G(x)\)（注意，这个是不严格的，只是这里恰好正确，不恰当的引入负指数会导致荒谬的结果），所以有 \(G(x) = e^{-\frac{1}{x}}F(x)\)

5、对偶思想

未能深刻理解，先咕咕咕了。

6、技巧

1、求导技巧。

对于一个简单函数 \(F(x)\) ，而且模数不是 \(998244353\) 的时候，我们可以考虑求导后比较，得到 \(O(n)\) 递推。

2、算子技巧

常见算子有：\(D\),\(\vartheta\)，算子构成群，当只有算子和单位元的时候可以对算子直接求 Poly，这类题目通常和斯特林相关。

3、行列置换技巧

当一个式子算不出来的时候，不妨把 \(O(n^2)\) 的那种矩阵画出来，看看行/列有没有封闭形式。

4、Ln/Exp 技巧

最经典问题是付公主的背包，这种思想在连乘中很常用。

7、经典问题

1、斯特林数

第一类斯特林数只要记得 \([x^a](e^x-1)^b\) 就行了，非常简单。

第二类斯特林数需要记两个，一个是 \([x^a]\prod_{i=0}^{b-1}(x+i)\)，另一个是 \([x^a]\frac{(-ln(1-x))^b}{a!}\)，两个可以互相推导，需要数学归纳法和分部积分。

对于转幂问题，通常是离散积分这类问题。

只要记得 \(x^n = \sum_{i=0}^{n}S(n,i)x^{\underline i}\) 即可。组合意义是：用不能放在一个框里的组合对象，拟合没有这个限制的组合对象。

下降幂就更智障了，直接 Poly 推导即可。