求教一道题目的解法

lyg_wangyushi

$\sum_{1}^{N}{k^x*x^k}$ mod (M) x,N,M 的值有用户输入 x,N,M 均为整数，1<=N,M<=$2*10^9$, 1<=x<=50 编写程序求这个表达式的值，有什么好的方法吗?谢谢。

无心人

怎么解释这个公式？

gxqcn

楼主表达式中的循环变量可是 $k $？ 即计算完整的表达式为：$\sum_{k=1}^{N}(x^k*k^x) \ mod(M)$

gxqcn

由于 M 比较小， 所以无需大数计算，也不需要什么高级算法， 只是中间都用模运算。 另外，“$x^k mod M$”可以作为中间结果保存下来， 为下次循环的计算加速。

lyg_wangyushi

时间限制只有1s钟的时间，k是循环变量，能在这么短的时间内求得吗？

lyg_wangyushi

对了,忘了说了,题目有多组测试数据,时间限制为1s钟

lyg_wangyushi

那天比赛的时候只有4个队过了这道题，应该不是暴力求解的吧，大家有好方法嘛 ？谢谢

mathe

我们可以考虑更加一般的情况 $\sum_{k=0}^Nk^xy^k(mod M)$ 记上式为f(x,y),那么$f(0,y)=(1-y^{N+1})/(1-y)$, $y*{df(x,y)}/{dy}=f(x+1,y)$ 通过这个递推式，我们可以通过反复计算微分，得到f(x,y)的表达式，然后最后将y=x代入就可以了。

无心人

我晕了 原来是这个式子啊？ 我前几天看到的是1N(xk*kx) mod M 我还纳闷呢 是不是GxQ回来了啊 这几天可公式都不正常显示啊

lyg_wangyushi

谢谢mathe的解答