2018 CCPC网络赛1005 HDU6442 GuGu Convolution

未分类

---

题意:
给定$A$,$B$,$n$,$p$,定义$f(x)=\sum_{i=0}^\infty \frac{A^i}{i!}x^i,g(x)=\sum_{i\ is\ odd} \frac{\sqrt{B}^i}{i!}x^i$,求$f$和$g$的卷积的$x^n$的系数乘$n!$的结果.答案一定可以化为$X*\sqrt{Y}$的形式,$Y$无平方因子.输出$X,Y$对$p$取模的结果.
数据范围: $1\leq A,B \leq 10^6,1\leq n \leq 10^{18},1\leq p \leq 10^9$.

解析:
根据公式直接计算答案:

$$\begin{align*} ans &= n!\sum_{i \ is \ odd,0\leq i \leq n} \frac{\sqrt{B}^i }{i!} \frac{A^{(n-i)}}{(n-i)!} \\ &= \sum_{i \ is \ odd,0\leq i \leq n} C_n^i\sqrt{B}^i A^{(n-i)} \end{align*}$$
这是$(A+\sqrt{B})^n$的二项展开式的$\sqrt{B}$的幂为奇数的部分,那么可以构造成:
$$\begin{align*} (A+\sqrt{B})^n-(A-\sqrt{B})^n &= \sum_{i=0}^nC_n^iA^i\sqrt{B}^{n-i} - \sum_{i=0}^nC_n^iA^i(-\sqrt{B})^{n-i} \\ &= 2*ans \end{align*}$$
设$(A+\sqrt{B})^n=a_n+b_n\sqrt{B}$,那么显然$(A-\sqrt{B})^n=a_n-b_n\sqrt{B}$,所以答案就是$b_n\sqrt{B}$.接下来考虑求解$b_n$.
$$\begin{align*} (A+\sqrt{B})^{n+1} &=(A+\sqrt{B})^n * (A+\sqrt{B}) \\ &= (a_n+b_n\sqrt{B})*(A+\sqrt{B}) \\ &= Aa_n+Bb_n+(a_n+Ab_n)\sqrt{B} \end{align*}$$
所以得到递推式$a_{n+1}=Aa_n+Bb_n,b_{n+1}=a_n+Ab_n$,用矩阵快速幂加速运算即可.
最后还需要注意一点,输出要求$X\sqrt{Y}$中$Y$无平方因子,因此求解出的$b_n\sqrt{B}$不一定就是最终答案,需要对$B$进行因子分解,把平方因子去掉.
时间复杂度$O(8logn+\sqrt{B})$