我的任务有效的解决方案需要

我只是解决了这一点，但想知道更有效的方式做到矩阵乘法我的任务有效的解决方案需要

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

我的任务有效的解决方案需要

回答

相关问题