萨姆我的总和^说明使用矩阵求幂

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

（链接到原始问题：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'项的。

任何人都可以提供任何链接或解释如何解决这种复发或如何形成初始矩阵，其权力将用于解决复发？

它是一个关于spoj的编程问题。如果不利用矩阵求幂，至少有人可以描述一个想法？

来源

2015-07-21 bytes1337

这似乎更像是一个数学问题，而不是像一个编程问题。 –

你可以发布你正在尝试解决的确切复发吗？ – IVlad

这似乎是一个数学问题，而不是一个编程问题。 – MikeMB

要在你的问题解决问题linked，我们可以利用一系列数学身份（S(p,k)是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)

来源

2015-07-26 03:13:03

我无法评论你的变换公式是否比天真的解决方案更有效，但如果它确实花费了你的程序超过1秒来计算示例输入的解决方案，它的方式比Navie C++方法慢（在我的机器上，天真的C++版本需要1,3 **毫秒** - 但我没有hakell编译器来测试你的）。您是否编译了启用编译器优化？顺便说一句：你知道，这个问题是用C++标记的，而不是haskell？ – MikeMB

其次，这可能是也可能不是一个很好的答案，但不是OP的问题（至少不是没有编辑的原始问题） - 至少在这里我没有看到任何矩阵。但考虑到这更像是[XY-Problem]（http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem），我认为这很好。 – MikeMB

@MikeMB我很感谢您的参与。您的Naive C++版本是否在1.3毫秒内计算'f（1,321）+ f（2,321）... + f（123456789,321）'的总和？我不这么认为 - 那将是7,620,789,436,823,655次操作（我的确是它，这是我的示例输出中的最后一项）。我认为OP确实要求提供其他想法，至少我是这样解释他/她的评论的，“你是否可以描述要接近的想法？” –

萨姆我的总和^说明使用矩阵求幂

回答

相关问题