求教一道题目的解法
\sum_{1}^{N}{k^x*x^k} mod (M)x,N,M 的值有用户输入 x,N,M 均为整数，1<=N,M<=2*10^9,1<=x<=50
编写程序求这个表达式的值，有什么好的方法吗?谢谢。 怎么解释这个公式？ 楼主表达式中的循环变量可是 k ？
即计算完整的表达式为：\sum_{k=1}^{N}(x^k*k^x) \mod(M) 由于 M 比较小，
所以无需大数计算，也不需要什么高级算法，
只是中间都用模运算。
另外，“x^k mod M”可以作为中间结果保存下来，
为下次循环的计算加速。 时间限制只有1s钟的时间，k是循环变量，能在这么短的时间内求得吗？ 对了,忘了说了,题目有多组测试数据,时间限制为1s钟 那天比赛的时候只有4个队过了这道题，应该不是暴力求解的吧，大家有好方法嘛 ？谢谢 我们可以考虑更加一般的情况
$\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回来了啊
这几天可公式都不正常显示啊 谢谢mathe的解答:)
页:
[1]