链接

注意到有一种最基本的容斥：有一些限制条件都必须满足，那么我们可以容斥，钦定一些限制没有满足，求出方案数再乘上容斥系数。这个当然可以用二项式反演来理解，但也可以有这么一种理解：考虑每个限制是否满足是一个bool值，那么一种方案的贡献是 ∏(1−bi)\prod(1-b_i)，其中如果第 ii 个限制没有满足则 bi=1b_i=1，否则 bi=0b_i=0。这样我们把这个式子拆开，就变成了 ∑S(−1)∣S∣∏i∈Sbi\sum\limits_{S}(-1)^{|S|}\prod\limits_{i\in S}b_i。这样刚才的过程就相当于在枚举 SS。

半在线卷积：bn=∑i+j=naibjb_n=\sum_{i+j=n}a_ib_j 的形式，即需要卷积完才能知道 bnb_n。
而求逆，ln，exp都可以表示成这样的形式，所以都有分治FFT的做法。
全在线卷积：即 an,bna_n,b_n 都是卷积完才能知道。这个可以注意到 ana_n 的卷积式中总有一项是 <n2<\frac{n}{2} 的，于是可以倍增套上半在线，可以做到相同的复杂度。

然而还讲了 O(nlog⁡nlog⁡log⁡n)O(\frac{n\log n}{\log\log n}) 的做法，这个感觉没有什么用啊，还是不要进坑了。而且还有结论是这个东西再来一个难以实现的优化之后可以做到 O(nlog⁡1+epsn)O(n\log^{1+eps}n) 的复杂度。

多项式求值：f(x0)=f(x)mod  (x−x0)f(x_0)=f(x)\mod(x-x_0)，因为取模即把 f(x)f(x) 表示为 q(x−x0)+rq(x-x_0)+r，这样代入 x0x_0 时就只剩 rr 了。然后分治即可。

回顾中国剩余定理：

x≡a1(modm1)x≡a2(modm2)...x≡ak(modmk)x\equiv a_1\pmod {m_1}\\x\equiv a_2\pmod {m_2}\\...\\x\equiv a_k\pmod {m_k}

其中模数两两互质。
这时我们的思路是对每个 ii 求一个单位元 cic_i 使得 ci≡[i=j](modmj)c_i\equiv [i=j]\pmod{m_j}，这样我们就可以构造解 ∑aici\sum a_ic_i。而我们设 M=∏mi,Mi=MmiM=\prod m_i,M_i=\frac{M}{m_i}，则 ci=MiMi−1c_i=M_iM_i^{-1}，其中 Mi−1M_i^{-1} 是 MiM_i 在模 mim_i 时的逆。因为互质所以逆一定存在。这样就可以求解了。
虽然我们有扩展中国剩余定理可以求模数不互质的情况，但是中国剩余定理因为它的形式优美，仍然有用武之地。

考虑多项式插值，本质上是

f(x)≡yi(modx−xi)f(x)\equiv y_i\pmod{x-x_i}

很多这样形式的同余方程的合并的问题。那么仍然可以套用中国剩余定理，这时我们求单位元

ci=[∏j=i(x−xj)mod  (x−xi)]−1∏j=i(x−xj)c_i=[\prod\limits_{j\not =i}(x-x_j)\mod (x-x_i)]^{-1}\prod\limits_{j\not =i}(x-x_j)

这里显然可以得到如果 xix_i 互不相同则逆一定存在，相当于满足了上面“互质”的条件。

注意设 M(x)=∏(x−xi),Mi(x)=M(x)x−xiM(x)=\prod(x-x_i),M_i(x)=\frac{M(x)}{x-x_i}，则 ∏j=i(x−xj)mod  (x−xi)\prod\limits_{j\not =i}(x-x_j)\mod (x-x_i) 其实就是 Mi(xi)M_i(x_i)（模 (x−xi)(x-x_i) 相当于求值）
Mi(x)=M(x)−M(xi)x−xiM_i(x)=\frac{M(x)-M(x_i)}{x-x_i}，套用洛必达法则（或者直接导数定义也行吧..），可以得到 Mi(xi)=M′(xi)M_i(x_i)=M'(x_i)。那么现在我们只需要对 M′(x)M'(x) 跑一个多点求值即可算出前面的一部分。求出这个之后后面就是比较trivial的分治，不再赘述。

也可以发现这个式子与拉格朗日插值公式完全一致。（是不是因为拉格朗日插值公式的内在原理就是中国剩余定理啊）

范德蒙德多项式的求值问题：∏i<j(xj−xi)\prod_{i<j}(x_j-x_i)
这个东西有一种显然的 O(nlog⁡3n)O(n\log^3n) 的做法，就是分治，然后考虑跨过mid的贡献，发现是把一边的数丢到另一边多点求值....
然而有更好的 O(nlog⁡2n)O(n\log^2n) 的做法。我们考虑每个 jj 与它之前的 ii 的贡献。还是考虑分治，我们希望分治到最底部 [j,j][j,j] 时的结果是 ∏i<j(x−xi)mod  (x−xj)\prod\limits_{i<j}(x-x_i)\mod (x-x_j)，那么我们在分治过程中在 [l,r][l,r] 维护 ∏i<l(x−xi)mod  ∏l≤j≤r(x−xj)\prod\limits_{i<l}(x-x_i)\mod\prod\limits_{l\leq j\leq r}(x-x_j) 即可。这样转移也是显然的。

关于 5\sqrt 5 一类的问题（一般是斐波那契数），如果 5\sqrt 5 在模意义下存在，那么解二次剩余即可。否则，我们可以扩域：a+b5a+b\sqrt 5，这样加法和乘法都显然，而逆元是 1a+b5=a−b5a2−5b2\frac{1}{a+b\sqrt 5}=\frac{a-b\sqrt 5}{a^2-5b^2}。我们可以发现当 5\sqrt 5 不存在且 a,ba,b 不全为 00 时 a2−5b2a^2-5b^2 一定不为 00。这样就保证了这个域是合法的。