Устройства со следующими условиями:

Question

Приведена матрица AxB с целыми числами> = 0. Сумма каждого столбца матрицы не должна уменьшаться при перемещении слева направо. Кроме того, сумма B ^я колонка (последняя колонка) меньше или равна A.

Найти число различных матриц такого типа для данных А и В.

Я пытался решить используя рекурсию и мемоизация следующего образом-

функции решения()

IS-

ll solve(ll i,ll curlevel) 
{ 
if(dp[i][curlevel]!=-1) 
    return dp[i][curlevel]; 
if(i<0) 
    return dp[i][curlevel]=0; 
if(curlevel==B) 
    return dp[i][curlevel]=test(i,c); 
if(curlevel>B) 
    return dp[i][curlevel]=0; 
ll ans=0; 
for(ll k=i;k>=0;k--) 
{ 
    ans+= test(i,A)* solve(k, curlevel+1); 
} 
return dp[i][curlevel]=ans; 
} 

тест функции определяются следующим образом- (Это вычисляет нет путей суммы = «суммы» может происходить как сумма отдельных неотрицательных чисел = «мест»)

ll test(ll sum,ll places) 
{ 
if(mem[sum][places] != -1) 
    return mem[sum][places]; 
if(sum==0) 
    return mem[sum][places]=1; 
if(places==0) 
    return mem[sum][places]=0; 
ll val=0; 
for(ll i=0;i<=sum;i++) 
{ 
    val+=test(sum-i,places-1); 
} 
return mem[sum][places]=val; 
} 

Этот метод, однако, слишком медленный.

Есть ли более быстрый способ сделать это (может быть, лучше комбинаторику подхода)

Answer 1

Вы предвычислять Перегородки массива - число разбиений множества А в неотрицательные части (включая нули) и порядок учета заказов (т.е. подсчет как 0 0 1, так и 0 1 0 и т. д.).

Редактировать: Partitions(k) = C(A + k - 1, A - 1)
Пример A = 4
Partitions[4] = C(7,3)=7!/(4!3!)=35
весь массив: Partitions = {1,4,10,20,35}
Для расчета разделов, использование таблицы - вращают треугольника Паскаля

1 1 1 1 1 
1 2 3 4 5 //sum of 1st row upto ith element 
1 3 6 10 15 //sum of 2st row 
1 4 10 20 35 //sum of upper row 

для A = 1000 вам нужно около 1000 * sizeof (int64) памяти (одна или две строки) и около 10^6 по модулю дополнений. Если вам нужно сделать расчеты для многих значений А, просто хранить всю таблицу (8 Мб)

Затем используйте эту формулу: // исправлен

S(columns, minsum) = Partitions[k] * Sum[k=minsum..A]{ S(columns - 1, k) } 
S(1,k) = Partitions[k] 
Result = Sum[k=0..A] { S[B,k] } 

Answer 2

Начиная с последней ячейки последнего столбца , если эта ячейка имеет значение A, то все остальные ячейки в последнем столбце должны быть равны 0, поэтому в этом случае последний столбец имеет 1 возможную компоновку.

Если последняя ячейка имеет значение A-1, то ячейка рядом с ней в одном столбце может быть 0 или 1, поэтому существует одна компоновка, в которой последний столбец суммируется с A-1 и A-1 механизмы, в которых столбец суммы к А.

в общем, рекурсивной функции:

NumberOfArrangementsOfColumn(cells_remaining, value_remaining){ 
    if(value_remaining == 0) return 1; 
    if(cells_remaining == 1) return value_remaining + 1; 
    int total = 0; 
    for(int sub_value = 1; sub_value <= value_remaining; sub_value++){ 
     total += 
      NumberOfArrangementsOfColumn(cells_remaining - 1, sub_value); 
    } 
    return total; 
} 

Эта функция будет определять количество механизмов для последнего столбца. Затем вам необходимо создать еще одну рекурсивную функцию для вычисления каждого из оставшихся столбцов, начиная со следующего до последнего столбца и т. Д. Для каждого возможного значения.