algorithm - 具有二元运算的巨大图形练习

Question

所以我遇到了以下问题:

让我们G是 2^N 的图表标记为 0 的顶点至 2^N-1 .这是一个有向无环图，以便有一条来自 a 的路径。至 b必须满足以下两个条件:

1. a < b
2. a XOR b (二进制)= 2^x , 其中x>=0

我需要确定长度为 K 的路径总数(所有边的长度为 1 )。 输入由 N 组成和 K .

计算长度路径数量的简单方法 K会看G与任何其他图形一样，并使用条件来确定连接了哪些顶点。但是，该任务需要 N和 K尺码 2<=K<=N<=100000 .

2^100000有点太多了，所以必须有更好的方法来计算这个。此外，我的执行时间仅限于 200女士。

示例:对于 N = 4和 K = 2 , 结果是 48 .

有什么想法吗？

Answer 1

所以基本上我们需要找到多少x0 < x1 < ... < xk < 2^N有这样的:

xi xor xi+1 = 2^x

请注意，对于 xor两个数是 2 的幂，xor 的结果必须恰好包含 1 位集。因此，这 2 个数字必须只有一个位置不同(否则，将在 xor 中设置更多位置，因为 xor 仅当操作数为不同位时才返回 1)。

假设我们从 0 开始.我们可以从它移动到任何标有 2 幂的节点.

然后，我们可以从该节点移动到在当前节点的设置位位置设置了位且在其他位置设置了位的任何节点。继续下去，考虑到我们必须按递增顺序生成序列。

例如:

000 -> 001 -> 011 -> 111
           -> 101 -> 111
    -> 010 -> 011 -> 111
           -> 110 -> 111
    -> 100 -> 101 -> 111
           -> 110 -> 111
=> 6 = 3! solutions

0000 -> 0001 -> 0011 -> 0111 -> 1111
                     -> 1011 -> 1111
             -> 0101 -> 1101 -> 1111
                     -> 0111 -> 1111
             -> 1001 -> 1011 -> 1111
                     -> 1101 -> 1111
=> 6 solutions
=> another 3*6 for the other 3 possibilities from 0000
=> 24 solutions

所以，为了得到一条长度为k的路径, 你需要从一个至少有 k 的整数开始取消设置 (0) 位。

所以你可以找出有多少n-bit整数至少有 k未设置位，找出有多少种可能性可以选择k从那些，并将答案乘以 k! .

找到多少n-bit整数正好 k'未设置位，可以使用二项式系数:

Binomial(n, k') = n! / [k'!*(n - k')!]

您还需要将其乘以 Binomial(k', k)为了决定哪个k您将要使用的位。

您需要对 k' = k to n 求和并将总和乘以 k! .

这些将是一些巨大的数字。我猜你被问及对质数取模的结果，在这种情况下你将不得不使用模乘逆。