как подсчитать все возможные подмножества, составляющие элементы, складываются до заданного числа с дублирующимися элементами

Question

Я дал несколько чисел, скажем, {a, b, c, d}, я могу использовать эти числа любое количество раз, чтобы сделать сумму 'N'. Я должен вычислить всю возможную комбинацию, скажем, «A», и я должен вернуть A% M, где M - некоторое большое простое число. ограничение, которое вызывает проблему для меня, составляет N <= 10 ^ 18. Размер множества {a, b, c, d ..} меньше 100. </p>

Я использую динамическое программирование для решения этой проблемы, но проблема в том, что я не могу использовать массив размером 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], и это дает нам A[100] после 8 умножений матриц. Поскольку все растет в геометрической прогрессии, теоретический ответ имеет абсурдно большие целые числа, но эти операции легко выполнить мод p.

Это выполнимо? Если n = 10**18, то у нас будет не более 60 делений пополам, каждый из которых при таком наивном подходе может иметь еще одно +1 умножение для 120 матричных операций. Если самый большой элемент набора равен 100, то есть около 2 миллионов на умножение матрицы (половину умножения, половину сложения) для 240 миллионов операций.

У вас впереди еще много работы. Но с этим матричным подходом это по крайней мере выполнимо.