algorithm - 如何计算元素的所有可能子集加起来等于给定数字的重复元素

Question

我已经给出了一些数字 {a,b,c,d}，我可以多次使用这些数字来得出总和“N”。我必须计算所有可能的组合，假设它是“A”，我必须返回 A%M，其中 M 是某个大质数。给我带来问题的约束是 N <= 10^18。集合 {a,b,c,d..} 的大小小于等于 100。

我正在使用动态规划来解决它，但问题是我不能使用 10^18 大小的数组，如果我不缓存预先计算的值，则会超过时间限制。

    #define M 1000000007
    long long solve(long long N, vector<long long>& v, vector<long long>& dp){
        if(N==0){
           return 1;
         }
         if(dp[N]!=-1){
               return dp[N];  
          }
         int n = v.size(); // maximum size of v <=100
         long long ans = 0;
         for(int i=0;i<n;i++){
                 if(N-v[i]>=0){
                     ans = (ans + solve(N-v[i],v,dp))%M; 
                  }
            }
          dp[N] = ans;
          return ans;

     }
    int main(){

        long long n, N;   // n: size of set , N: expected sum
        cin>>n>>N;
        vector<long long>v(n);
        for(int i=0;i<n;i++){
             cin>>v[i];
         }
        long long ans  = 0;
        vector<long long>dp(N+1,-1);
        for(int i = 0;i<n;i++){
                if(N-v[i]>=0){
                     ans = (ans + solve(N-v[i],v,dp))%M; 
                  }
           }
        cout<<ans<<endl;
     }

如何优化它以在不耗尽时间的情况下处理总和 10^18。

Answer 1

为了举例，我假设您的集合是 {1, 1, 3} 并且我们要计算第 100 项。但这种方法通常会奏效。

让 k 成为你的集合中的最大值。设 s[i] 为使 i 求和的方法数。我们的起始条件是 s[-k+1] = 0, s[-k+2]= 0, ..., s[-1] = 0 但 s[0] = 1。 {a, b, c, ...} 的归纳步骤是 s[n] = s[n-a] + s[n-b] + s[n-c] + ....

但现在重新概念化它。考虑向量 v[n] = (s[n-k+1], s[n-k+2], ... + s[n])。设 A[m] 是您必须乘以得到向量 v[n+m] = (s[n+m-k+1], s[n +m-k+2], ..., s[n+m])。我会假设它存在。如果您想解决斐波那契数列的一般证明。

现在我们需要关于这些矩阵的两个事实。

第一个是 A[m1 + m2] = A[m1] * A[m2]。要看到这一点，只需注意对于所有 n，(A[m1] * A[m2])(v[n]) = A[m1]( A[m2]( v[ n] ) ) = A[m1]( v[n + m2] ) = v[n + m2 + m1] = A[m1 + m2]( v[n] )。

第二个是我们可以很容易地计算A[1]。它的上对角线全为 1，最后一行在我们集合中的任何地方都有 +1。 (或者如果该元素在我们的集合中出现两次，则为 +2，正如我在示例中确定的那样。)所以对于我们的示例，我们有:

[0 1 0]   [ v[n-2] ]   [ v[n-1] ]
[0 0 1] * [ v[n-1] ] = [ v[n]   ]
[1 0 2]   [ v[n]   ]   [ v[n+1] ]

初始矩阵为A[1]。

现在假设我们要计算s[100]。那是 v[100] 的最后一个条目。但现在我们按如下方式减半:A[100] = A[50] * A[50]。 A[50] = A[25] * A[25]。 A[25] = A[12] * A[13]。 A[13] = A[1] * A[12]。 A[12] = A[6] * A[6]。 A[6] = A[3] * A[3]。 A[3] = A[2] * A[1]。最后，A[2] = A[1] * A[1]。但是我们有 A[1]，这在 8 次矩阵乘法后得到了 A[100]。由于一切都呈指数增长，理论上的答案有大得离谱的整数，但这些操作很容易做 mod p。

这可行吗？如果 n = 10**18 我们最多有大约 60 次减半，使用这种天真的方法，每一次减半都可以有另一个 +1 乘法以进行 120 次矩阵运算。如果该集合的最大元素是 100，则每次矩阵乘法(一半乘法，一半加法)大约有 200 万次，需要 2.4 亿次运算。

您还有很多工作要做。但使用这种矩阵方法，它至少是可行的。