我的任務有效的解決方案需要

我只是解決了這一點，但想知道更有效的方式做到矩陣乘法我的任務有效的解決方案需要

M = | 1 0 3 | 
    | 1 0 2 | 
    | 0 5 0 |

F [N] = M^N

我已經實現了使用Exponentiation_by_squaring

這樣更有效嗎？

來源

2014-09-04 HybrisFreelance

@DavidPostill爲什麼選擇OT？優化和性能是這裏的常見標籤。 – maaartinus 2014-09-04 07:08:19

我想，這實際上更適合數學，因爲有一個封閉的表單解決方案。另一個可能性：您可以通過推導兩個步驟的公式來加速程序兩次。這可以重複... – maaartinus 2014-09-04 07:13:46

@DavidPostill其他人將它發送到CR。如果你問我，那全是BS。 – maaartinus 2014-09-04 07:18:14

我想，這實際上更適合數學，因爲有一個封閉的表單解決方案。它的系統是Linear homogeneous recurrence relations with constant coefficients。

另一個posibility：您可以通過推導公式兩步兩次加速的程序，即通過RR(i-2)表達RR(i)等等等等

而且可以重複這樣的，所以你可以跳快得多。

來源

2014-09-04 07:19:06 maaartinus

一個問題是您的計算溢出。如果您運行K = 1和J = 9，則得到-334328541#510576792#-817751931。
最簡單的修復方法是% 1000000006 in calculateProduction。

關於效率，我會在執行矩陣乘法時考慮這個問題。你開始與載體（即1×3的矩陣）：

3 1 0

，並在每個步驟中，您乘以（MOD 1000000006）與基體：

1 1 0 
0 0 5 
3 2 0

我們稱之爲矢量V和矩陣M.基本上你需要計算V * M ^N。由於矩陣乘法是關聯的，就可以計算出中號^Ñ第一，且行遞歸：
中號^Ñ =（M ^N/2）如果N爲偶數，或
中號^Ñ = M *（M ^[N/2]）如果N爲奇數

來源

2014-09-04 08:37:03 aditsu

我也嘗試過..但沒有得到suggess – HybrisFreelance 2014-09-04 08:39:50

是的，我已經認爲這個算法，但問題矩陣求冪可能需要時間.. 你可以有更好的想法矩陣求冪算法（動態編程） – HybrisFreelance 2014-09-05 12:47:29

@ ankit337我已經解釋瞭如何輕鬆進行矩陣求冪，您是否閱讀了我的答案的最後部分？ – aditsu 2014-09-05 20:08:17

不需要計算MM。這就是爲什麼：

PP[i] = 5*MM[i-1] = 5*(RR[i-2] + 2*PP[i-2]) 
RR[i] = RR[i-1] + 3*PP[i-1] = (RR[i-2] + 3*PP[i-2]) + 3*PP[i-1]

請參閱？你不需要在每一步計算MM。這應該是算法：

public class RecurrenceMachine { 
    private static final int max = 1000000006; 

    public String calculate(int k, int j) { 
     long n = k * j; 
     if (n < 1) 
      return "error"; 
     long RRi2 = 3; 
     long PPi2 = 0; 
     long RRi1 = 3 + 3 * PPi2; 
     long PPi1 = 5 * 1; 
     if (n == 1) 
      return RRi1 + "##" + (RRi2 + 2 * PPi2) + "##" + PPi1; 
     Long PPi = (long) 0, RRi = (long) 0, temp; 
     int i; 
     for (i = 2; i <= n; i++) { 
      temp = RRi2 + 2 * PPi2; 
      PPi = 5 * temp; 
      if (PPi >= max) 
       PPi %= max; 
      RRi = temp + PPi2 + 3 * PPi1; 
      if (RRi >= max) 
       RRi %= max; 
      RRi2 = RRi1; 
      PPi2 = PPi1; 
      RRi1 = RRi; 
      PPi1 = PPi; 
     } 
     return RRi + "##" + (RRi2 + 2 * PPi2) % max + "##" + PPi1; 
    } 
}

我只用小的值試過，它似乎工作。

來源

2014-09-04 12:19:07 Ariel

感謝您的解決方案。您在一個級別上改進了代碼，但對於大型輸入，其代碼幾乎與我的代碼相同。 – HybrisFreelance 2014-09-05 12:25:57

@ ankit337你可以給我一些大的輸入，所以我可以嘗試自己嗎？ – Ariel 2014-09-05 16:47:01

當然..這裏的條件是'1 <= K，J <= 10^6' 所以你可以從這個最大值作爲輸入 – HybrisFreelance 2014-09-06 08:14:54

我的任務有效的解決方案需要

回答

相關問題