薩姆我的總和^說明使用矩陣求冪

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確實要求提供其他想法，至少我是這樣解釋他/她的評論的，「你是否可以描述要接近的想法？」 –

薩姆我的總和^說明使用矩陣求冪

回答

相關問題