q-二项式定理
Ruizhangj
·
·
个人记录
q-二项式定理
要线性求出下面式子的每一项：
F(x)=\prod_{i=1}^{n}(1+q^ix)
显然有：
F(qx)(1+qx)=F(x)(1+q^{n+1}x)
设
F(x)=\sum_{i=0}^{n}f_ix^i
对比等式两边[x^k]：
\begin{aligned}
q^kf_k+q^kf_{k-1} & =f_k+q^{n+1}f_{k-1}\\
f_k & =\frac{q^{n+1}-q^k}{q^k-1}f_{k-1}
\end{aligned}
现在可以O(n)递推了，但是发现在模意义下有可能出现q^k-1\equiv 0 \mod P，此时递推就错了。
假设q的阶为\alpha，不难发现只有当\alpha|k时才会出现这种情况。更深入地，q^{\alpha}-1是导致问题的根本原因，那么可以提取分式上下的q^{\alpha}-1约分来解决问题。
可以发现，若k=r\alpha，那么q^k-1=(q^\alpha-1)r，在分式上下提取q^\alpha-1，用一个计数器来约分即可。
线性求逆元。