一道有趣的 q-analog 题
moongazer
·
·
个人记录
EI 鸽鸽太神了！@水军带你飞 鸽鸽太神了！
给定 n \le 10^9，对于所有 r \le 10^6 求：
f_r=\sum_{i = 0} ^ n \binom{i}{r}_q (-1)^{n-i} \binom{n}{i}
[r!]_qf_r&=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}[i^{\underline r}]_q\\
&=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}\prod_{j=0}^r(1-q^{i-j})\\
&=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}\prod_{j=0}^r(1-q^{-j}q^i)
\end{aligned}
令 p=q^{-1}，我们对 p 使用 q-binomial theorem
[r!]_qf_r&=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}\prod_{j=0}^r(1-p^jq^i)\\
&=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}\sum_{j=0}^r\binom{r}{j}_pp^{j(j-1)/2}(-q^i)^j\\
&=\sum_{j=0}^r\binom{r}{j}_pp^{j(j-1)/2}(-1)^j\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}q^{ij}\\
&=\sum_{j=0}^r\binom{r}{j}_pp^{j(j-1)/2}(-1)^j(q^j-1)^n
\end{aligned}
之后的事情便是把对 r 的贡献拆成 j 和 r-j 两部分，做个卷积即可。