Сумма следующих рядов ncr в O (1) временной сложности

Question

Есть несколько запросов вида

Q (n, m) = (nC1 * mC1) + (nC2 * mC2) + (nC3 * mC3) ... (nCk * mCk) где к = мин (п, т)

Как найти значение Q (n, m) в O (1) сложность времени.

Я пытался предварительно вычислить матрицу ncr [N] [N] и dp [N] [N] [N], где dp[n][m][min(n,m)] = Q(n,m).

Это предварительное вычисление занимает O (N ^ 3) времени, а на запросы можно ответить в O (1) раз. Но я ищу подход, при котором предварительное вычисление не должно занимать больше времени O (N ^ 2).

Answer 1

Решение для начала с C (n, 0) * C (m, 0) кажется довольно простым

Q0(n,m) = C(n+m, m)

Так что для вашей формулировки просто вычтите 1

Q(n,m) = C(n+m, m) - 1

Пример: n = 9, m = 5

Точечное произведение 9-го и 5-го рядов треугольника Паскаля равно

1   9     36    84    126   126  84  36  9  1
1   5     10    10    5     1
1 + 45 +  360 + 840 + 630 + 126                = 2002    = C(14,5)

Это может быть доказано с помощью математической индукции, начиная с Q (n, 1), но выражения довольно длинные.

Я обнаружил поистине изумительную демонстрацию этого предположения о том, что этот край слишком узок, чтобы вместить © Fermat;)