algorithm - a1 x1 + a2 x2 +…+ an x​​n = k(k <= 10 ^ 18)的正解数

Question

问题是a1 x1 + a2 x2 + .... + an x​​n = k的约束个数:1)ai> 0 and ai <= 15 2)n> 0 and n <= 15 3)xi> = 0我能够制定一个动态编程解决方案，但对于n> 10 ^ 10，它运行时间过长。请指导我获得更有效的姿态。
代码

int dp[]=new int[16];
        dp[0]=1;
        BigInteger seen=new BigInteger("0");
        while(true)
        {
            for(int i=0;i<arr[0];i++)
            {
                if(dp[0]==0)
                    break;
                dp[arr[i+1]]=(dp[arr[i+1]]+dp[0])%1000000007;
            }
            for(int i=1;i<15;i++)
                dp[i-1]=dp[i];
            seen=seen.add(new BigInteger("1"));
            if(seen.compareTo(n)==0)
            break;
        }
        System.out.println(dp[0]);

arr是包含系数的数组，答案应为mod 1000000007，因为不适合int的方式数量。

Answer 1

实际问题的更新:

实际问题要简单得多。但是，如果不完全破坏它，就很难有所帮助。

将其分解为基本要素，问题是

给定k个不同的正整数L1，...，Lk和一个非负整数n，有多少个不同的有限序列(a1，...，ar)使得1.对于所有i(1 <= i <= r) ，ai是Lj之一，并且2。a1 + ... + ar = n。 (换句话说，仅使用给定的Lj组成n的数量。)

为方便起见，您还被告知所有Lj均≤15(因此k≤15)，n≤10 ^ 18。并且，为了使整个计算可以使用64位整数来执行(序列数随n呈指数增长，您将没有足够的内存来存储大n的确切数)，您只应计算余数序列计数取模1000000007。

要解决此问题，请首先查看最简单的情况。最简单的情况是仅给出一个L，那么如果n是L的倍数，则显然存在一个可允许的序列，如果n mod L!= 0，则没有可允许的序列。这还没有帮助。因此，考虑下一个最简单的情况，给出两个L值。假设它们是1和2。

0具有一种成分，空序列:N(0)= 1

1具有一种成分，(1):N(1)= 1

2具有两个成分，(1,1)； (2):N(2)= 2

3具有三个组成，(1,1,1);(1,2);(2,1):N(3)= 3

4具有五个成分，(1,1,1,1);(1,1,2);(1,2,1);(2,1,1);(2,2):N(4) = 5

5具有八个成分，(1,1,1,1,1);(1,1,1,2);(1,1,2,1);(1,2,1,1);(2 ，1,1,1);(1,2,2);(2,1,2);(2,2,1):N(5)= 8

您现在可能会看到它，或者需要更多术语，但是您会注意到您得到了斐波那契数列(移位了一个)，N(n)= F(n + 1)，因此序列N(n)满足递归关系
N(n)= N(n-1)+ N(n-2)(对于n> = 2；我们尚未证明，到目前为止，这是一个基于模式斑点的假设)。现在，不用计算很多值就能看到吗？当然，有两种类型的允许序列，以1结尾和以2结尾。由于可允许序列的划分仅限制了最后一个元素ad的数量。 seq。总和为n并以1结尾的是N(n-1)和ad的数量。 seq。总和为n并以2结尾的是N(n-2)。

假设L1 = Lk，这种推论会立即得到概括

N(n)= N(n-L1)+ N(n-L2)+ ... + N(n-Lk)

如果我们只对N(n)％m感兴趣，则可以用明显的解释。

嗯，那个线性递归仍然让计算N(n)成为O(n)任务吗？
是的，但是研究一些提到的关键字会很快导致只需要O(log n)个步骤的算法;)

用于误解问题的算法，不再适用，但可能仍然很有趣:

这个问题看起来有点像SPOJish，所以我不会给出完整的算法(至少在我搜索一下它是否是竞赛问题之前，至少不会)。我希望在描述中没有遗漏任何限制，例如，此类表示的排列仅应对计数作出贡献，这将使问题严重复杂化。因此，我将1*3 + 2*4 = 11和2*4 + 1*3 = 11视为两个不同的解决方案。

首先是一些符号。对于m个元组，让< | >表示规范双线性对，即<a|x> = a_1*x_1 + ... + a_m*x_m。对于正整数B，令A_B = {1, 2, ..., B}为不超过B的正整数集。令N表示自然数集，即非负整数。
对于0 <= m, k和B > 0，让C(B,m,k) = card { (a,x) \in A_B^m × N^m : <a|x> = k }。

然后，您的问题是找到\sum_{m = 1}^15 C(15,m,k)(模1000000007)。

为了完整起见，让我们提到C(B,0,k) = if k == 0 then 1 else 0，它可以在理论上有所帮助。对于正数的情况，我们很容易找到递归公式

C(B,m+1,k) = \sum_{j = 0}^k C(B,1,j) * C(B,m,k-j)

通过归纳，C(B,m,_)是m个因子C(B,1,_)的卷积¹。计算直到k的两个已知函数的卷积就是O(k^2)，因此，如果C(B,1,_)是已知的，则给出了O(n*k^2)算法来计算C(B,m,k), 1 <= m <= n。小k可以，但是我们的星系不会活着看到您以这种方式计算C(15,15,10^18)。那么，我们可以做得更好吗？好吧，如果您熟悉Laplace变换，就会知道类似的变换会将卷积乘积转换成点积，这很容易计算。但是，尽管在这种情况下转换很容易计算，但逆运算却并非如此。还有其他想法吗？为什么，是的，让我们仔细看看C(B,1,_)。

C(B,1,k) = card { a \in A_B : (k/a) is an integer }

换句话说，C(B,1,k)是k的除数不超过B的数量。让我们用d_B(k)表示。立即清楚1 <= d_B(k) <= B。对于B = 2，显然是d_2(k) = 1 if k is odd, 2 if k is even。且仅当d_3(k) = 3可被2和3整除时，才能使用k，因此iff k是6的倍数，并且当且仅当2、3之一将d_3(k) = 2除而不是另一方(即iff k和最后k % 6 \in {2,3,4} iff) 2和3都不除以k，即iff d_3(k) = 1，iff gcd(k,6) = 1。因此，我们已经看到k % 6 \in {1,5}在周期2上是周期性的，d_2在周期6上是周期性的。通常，像推理一样，对于所有B来说d_3都是周期性的，最小正周期将d_B除以。

给定B!的任何正周期P，我们可以在卷积中分解总和(k = q * P + r，0 <= r

C(B,m+1, q*P+r) = \sum_{c = 0}^{q-1} (\sum_{j = 0}^{P-1} d_B(j)*C(B,m,(q-c)*P + (r-j)))
                + \sum_{j = 0}^r d_B(j)*C(B,m,r-j)

C(B,1,_) = d_B函数不再是C(B,m,_)的周期性函数，但是有一些简单的公式可以从m >= 2获得C(B,m,q*P+r)。因此，对于已知到P的C(B,m,r)和C(B,1,_) = d_B，计算直到P的C(B,m,_)是C(B,m+1,_)任务²，获取任意大k的计算O(P^2)所需的数据，需要m个这种卷积，因此就是C(B,m+1,k)。

然后找到O(m*P^2)的C(B,m,k)和任意大的k是1 <= m <= n，时间上是O(n^2*P^2)，空间上是O(n^2*P)。
对于B = 15，我们有15! = 1.307674368 * 10 ^ 12，因此将其用于P是不可行的。幸运的是，d_15的最小正周期要小得多，因此您可以获得一些可行的方法。从粗略的估计来看，我仍然希望C(15,15,k)的计算花费的时间要比数秒更适合以小时为单位的小时数，但这是对O(k)的改进，后者需要花费几年的时间(对于k在10 ^ 18范围内)。

¹这里使用的卷积是(f \ast g)(k) = \sum_{j = 0}^k f(j)*g(k-j)。
²假设所有算术运算均为O(1)；如果像在OP中那样只需要模数M> 0的残差，那么如果所有中间计算都以模M进行，则成立。