O(1) 时间复杂度的以下 ncr 系列的总和
Sum of the following ncr series in O(1) time complexity
有多个
形式的查询
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) 时间的方法。
从 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 ;)
有多个
形式的查询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) 时间的方法。
从 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 ;)