java - 迭代前缀和的结果

Question

大小为 s + 1 的数组初始化为 a[i] = i对于 0 <= i < s , a[s] = 0 .然后我迭代地使用动态规划对数组的值求和，从最大到最小，这样做 t次。结果很快变大，所以我减少了一些模数 modulus .

如果s = 10 ，数组看起来像这样:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

[0, 45, 44, 42, 39, 35, 30, 24, 17, 9, 0]

[0, 45, 89, 131, 170, 205, 235, 259, 276, 285, 0]

等等。

在 t 之后迭代 我对数组的极端非零值感兴趣。我的算法明确地执行此操作，导致时间复杂度为 O(s*t) .是否有任何算法可以以更好的时间复杂度产生这些值中的一个(或两个)？具体来说，我在考虑是否可以进行矩阵求幂，将时间复杂度降低到 O(s*log(t)) ，但实际上任何方法和优化都是受欢迎的。

我的代码:

public class ArraySummation{

     public static void main(String []args)
     {
        int s = 10;
        long t = 10;
        
        long modulus = 1000000;
        
        long [] a = new long [s + 1];
        for (int i = 1 ; i < s ; i++)
            a[i] = i;

        for (int i = 2 ; i <= t ; i++)
        {
            if ((i & 1) == 1)
                for (int j = 1 ; j < a.length - 1 ; j++)
                {
                    a[j] += a[j - 1];
                    if (a[j] >= modulus)
                        a[j] -= modulus;
                }

            else
                for (int j = a.length - 2 ; j >= 1 ; j--)
                {
                    a[j] += a[j + 1];
                    if (a[j] >= modulus)
                        a[j] -= modulus;
                }
        }

        System.out.println(a[1]);
        System.out.println(a[s - 1]);
     }
}

Answer 1

对于 s=10 可以在 OEIS https://oeis.org/A030113 中找到作为线性递归。

对于所有的s，还有一个矩阵形式的公式

(PARI) k=9; M(k)=matrix(k, k, i, j, if(1-sign(i+j-k), 0, 1)); v(k)=vector(k, i, 1); a(n)=vecmax(v(k)*M(k)^n)

矩阵构造示例

Matrix construction

解释 矩阵 M 与矩阵 T 相乘，结果矩阵 R(简称:M . T = R)

• R的第一列是T的最后一列
• R的第二列是T的最后一列和倒数第二列的总和
• ...
• R的最后一列是T所有列的总和

因此问题的加法过程是通过矩阵乘法完成的，但初始化a[i] = 1。在第一轮 M^2 之后，最后一列包含问题的初始化 a[i] = i

M^2

根据参数 s、t，最好使用 M^8 = M^4 等矩阵求幂。 M^4 = M_4 。 M_4 , M^4 = M^2 。 M^2 = M_2 。 M_2，其中 M_2 和 M_4 可以重复使用。因此，我们可以得到结果，而不是仅进行 3 次乘法的 8 次矩阵乘法运算。

复杂度为 O(s^2 * log(t))