相邻位计数

Question

这是来自 spoj 的问题，其中指出

对于 n 位 x1,x2,x3,...,Xn 的字符串 字符串的相邻位数 (AdjBC(x)) 由下式给出

X1*X2 + X2*X3 + X3*X4 + ... + Xn-1 * Xn

计算 1 的次数 位与另外 1 位相邻。为了 示例：

AdjBC(011101101) = 3
AdjBC(111101101) = 4
AdjBC(010101010) = 0

，问题是：编写一个程序，以整数 n 和 k 作为输入，并返回满足 AdjBC(x) = k 的 n 位（共 2ⁿ）中的位串 x 的数量。

我不知道如何解决这个问题。你能帮我解决这个问题吗？

谢谢

Answer 1

作为提示，您可以将其分为两种情况：以 0 结尾的数字和以 1 结尾的数字。

def f(n, k):
    return f_ending_in_0(n, k) + f_ending_in_1(n, k)

def f_ending_in_0(n, k):
    if n == 1: return k == 0
    return f(n - 1, k)

def f_ending_in_1(n, k):
    if n == 1: return k == 0
    return f_ending_in_0(n - 1, k) + f_ending_in_1(n - 1, k - 1)

这会给出正确的输出，但需要很长时间才能执行。您可以应用标准动态编程或记忆技术来使其执行得足够快。

Answer 2

我迟到了，但我有一个线性时间复杂度的解决方案。

对我来说这更像是一个数学问题。您可以阅读我写的这篇博客文章中的详细解决方案。以下是简要概述。我希望我可以放一些 LaTeX，但 SO 不允许这样做。

假设对于给定的n和k，我们的答案由函数f(n,k)给出。使用乞丐法，我们可以得到以下公式

f(n,k) = SUM C(k+a-1,a-1)*C(n-k+1-a,a)，其中 a 从 1 运行到 (n-k+1)/2

这里 C(p,q) code> 表示二项式系数。

因此，为了得到答案，我们必须计算 a 每个值的二项式系数。我们可以预先计算二项式表。由于我们必须计算表格，因此这种方法将在 O(n^2) 内给出我们的答案。

我们可以通过使用递归公式 C(p,q) = (p * C(p-1,q-1))/q 来计算二项式系数的当前值，从而提高时间复杂度它们在上一个循环中的值。

我们的最终代码如下所示：

long long x=n-k, y=1, p=n-k+1, ans=0;
ans += x*y;

for(int a=2; a<=p/2; a++)
{
    x = (x*(p-2*a+1)*(p-2*a+2))/(a*(p-a+1));
    y = (y*(k+a-1))/(a-1);
    ans += x*y;
}

您可以在我的 中找到完整的可接受的解决方案GitHub 存储库。

Answer 3

通常在组合问题中，查看它产生的值集会有所帮助。我用蛮力计算出了下表：

  k   0   1   2   3   4   5   6
n +----------------------------
1 |   2   0   0   0   0   0   0
2 |   3   1   0   0   0   0   0
3 |   5   2   1   0   0   0   0
4 |   8   5   2   1   0   0   0
5 |  13  10   6   2   1   0   0
6 |  21  20  13   7   2   1   0
7 |  34  38  29  16   8   2   1

第一列是我们熟悉的斐波那契数列，满足递推关系 f(n, 0) = f(n-1, 0) + f(n-2, 0)

其他列满足递推关系f(n, k) = f(n - 1, k) + f(n - 1, k - 1) + f(n - 2, k) - f(n - 2, k - 1)

有了这个，您可以进行一些动态规划：

INPUT: n, k
row1 <- [2,0,0,0,...] (k+1 elements)
row2 <- [3,1,0,0,...] (k+1 elements)
repeat (n-2) times
  for j = k downto 1 do
    row1[j] <- row2[j] + row2[j-1] + row1[j] - row1[j-1]
  row1[0] <- row1[0] + row2[0]
  swap row1 and row2
return row2[k]