algorithm - O(1) 时间复杂度的以下 ncr 系列的总和

Question

有多个表单查询

Q(n,m) = (nC1*mC1) + (nC2*mC2) + (nC3*mC3) ... (nCk*mCk) where k=min(n,m)

如何在 O(1) 时间复杂度内找到 Q(n,m) 的值。

我尝试预先计算 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 ;)