Problem. P

题意简述:

给定(n,m,u,v),求(sumlimits_{sumlimits_{i=0}^mk_i=n}prodlimits_{i=0}^m(u+iv)^{k_i}(k_iinmathbb N)),答案对(1000000007)取模。

数据范围:

(nle10^{18},0le u,vle10^9,mle10^6)

解法:

首先我们知道(ans=[x^{n+m+1}]prodlimits_{k=0}^mfrac x{1-(u+vk)x})

方法(1)

(F(z)=prodlimits_{k=0}^mfrac z{1-(u+vk)z}),考虑形式Laplace-Borel逆变换。

[widehat F(z)=frac1{2pi}int_{-pi}^{pi}F(ze^{-ivartheta})e^{e^{ivartheta}}mathrm dvartheta ]

(zeta=e^{ivartheta}),考虑换元积分法。

[widehat F(z)=frac1{2pi i}int_{|zeta|=1}frac{e^{zeta}}{zeta}F(frac z{zeta})mathrm d{zeta}=frac1{2pi i}int_{|zeta|=1}frac{e^{zeta}}{zetaprodlimits_{j=0}^m(frac{zeta}z-(u+vj))}mathrm d{zeta},quad|z|<frac1{|u+vm|} ]

考虑利用留数定理进行计算。

[widehat F(z)=sumlimitsoperatorname{Res}(f(zeta),a_i),f(zeta)=frac{e^{zeta}}{zetaprodlimits_{j=0}^m(frac{zeta}z-(u+vj))} ]

很显然(f(zeta))仅有(m+2)个奇点,且这些都是单极点。计算得到:

[egin{aligned} operatorname{Res}_{zeta=0}f(zeta)&=frac{(-1)^{m+1}}{prodlimits_{j=0}^m(u+vj)}\ operatorname{Res}_{zeta=(u+vk)z}f(zeta)&=frac{e^{u+vk}}{(u+vk)prodlimits_{j e k}v(k-j)}=frac{(-1)^{m-k}e^{u+vk}}{(u+vk)v^mk!(m-k)!}=frac{(-1)^{m-k}}{v^mm!}{mchoose k}frac{e^{(u+vk)z}}{(u+vk)} end{aligned} ]

利用二项式定理可以得到:

[widehat F(z)=intfrac{e^{uz}(e^{vz}-1)^m}{m!v^m}mathrm dz ]

那么我们有:

[ans=[z^{n+m}]frac{e^{uz}(e^{vz}-1)^m}{m!v^m}=frac{sumlimits_{k=0}^m(-1)^{m-k}{mchoose k}(u+vk)^{n+m}}{m!v^m} ]

方法(2)

构造多项式列({F_0(x),cdots}),其中(F_i(x)=frac1{1-(u+vi)x})

我们对其定义差分运算:

[Delta^0F_i(x)=F_i(x),Delta^jF_i(x)=Delta^{j-1}F_{i+1}(x)-Delta^{j-1}F_i(x) ]

利用数学归纳法不难得到:

[Delta^tF_k=frac{t!v^tx^t}{prodlimits_{i=k}^{k+t}1-(u+vi)x} ]

因此我们有:

[ans=frac1{m!v^m}[x^{n+m}]Delta^mF_0(x) ]

我们知道:

[[x^{n+m}]F_k(x)=(u+vk)^{n+m} ]

根据差分的定义不难得到:

[Delta^tF_k(x)=sumlimits_{i=0}^t(-1)^{t-i}{tchoose k}F_{k+t}(x) ]

因此我们可以得到:

[ans=frac1{m!v^m}[x^{n+m}]Delta^mF_0(x)=frac{sumlimits_{k=0}^m(-1)^{m-k}{mchoose k}(u+vk)^{n+m}}{m!v^m} ]

直接快速幂即可做到(O(mlog n))

原文地址:https://www.cnblogs.com/cjoierShiina-Mashiro/p/12923729.html