使用矩阵求幂的 i^k 之和

Question

f(n) is defined as: f(n) = 1^k+2^k+3^k+...+n^k, so it is the sum of the k-th power of all natural numbers up to n.

In this problem you are about to compute,

f(1) + f(2) + f(3) + ... + f(n)

1 ≤ n ≤ 123,456,789 and 0 ≤ k ≤ 321

( Link 到原题：http://www.spoj.com/problems/ASUMHARD/Matrix )

一种天真的算法，逐项计算运行速度太慢，所以我想到尝试解决递归关系。

天真的方法：

total = 0
for i = 1 to n:
    for j = 1 to i:
        total += j^k
return total

求幂可以用来求解线性递归。我知道如何解决线性递归问题，例如：

f(n) = f(n-k1) + f(n-k2) + ... + constant

但是我找不到任何关于如何解决像

这样的重复问题的信息

f(n) = f(n-k1) + f(n-k2) + ... + n^m

或

f(n) = f(n-k1) + f(n-k2) + ... + n*m

或

f(n) = f(n-k1) + f(n-k2) + ... + k^n

即涉及 'n' 个术语。

这样的递归如何求解，或者如何形成初始矩阵，其幂将用于求解递归？如果不利用矩阵求幂，有人至少可以描述一下如何处理它吗？

Answer 1

解决问题linked in your question, we can use a series of mathematical identities (S(p,k) are Stirling Numbers of the Second Kind):

(1)

(2)

(3)

最后，利用身份，

我们得到：

(4)

Haskell代码：

import Math.Combinat.Numbers

f n k
  | k == 0    = mod (div (n * (n + 1)) 2) 1234567891
  | otherwise = sum 
              $ map (\i -> stirling2nd k i 
                           * factorial i 
                           * binomial (n + 2) (i + 2) `mod` 1234567891) [1..k]

main = print (map (\(n,k) -> f n k) [(2,3),(10,3),(3,3),(100,0),(100,1),(123456789,321)])

输出：

*Main> main
[10,7942,46,5050,171700,193476340417]
(1.08 secs, 1374079760 bytes)

使用矩阵求幂的 i^k 之和

Sum of sum of i^k using matrix exponentiation

algorithm

recurrence

matrix