求教一道题目的解法

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的解答