string - CodeJam 2014 : How to solve task "New Lottery Game"?

Question

我想知道 New Lottery Game 的有效方法问题。

The Lottery is changing! The Lottery used to have a machine to generate a random winning number. But due to cheating problems, the Lottery has decided to add another machine. The new winning number will be the result of the bitwise-AND operation between the two random numbers generated by the two machines.

To find the bitwise-AND of X and Y, write them both in binary; then a bit in the result in binary has a 1 if the corresponding bits of X and Y were both 1, and a 0 otherwise. In most programming languages, the bitwise-AND of X and Y is written X&Y.

For example: The old machine generates the number 7 = 0111. The new machine generates the number 11 = 1011. The winning number will be (7 AND 11) = (0111 AND 1011) = 0011 = 3.

With this measure, the Lottery expects to reduce the cases of fraudulent claims, but unfortunately an employee from the Lottery company has leaked the following information: the old machine will always generate a non-negative integer less than A and the new one will always generate a non-negative integer less than B.

Catalina wants to win this lottery and to give it a try she decided to buy all non-negative integers less than K.

Given A, B and K, Catalina would like to know in how many different ways the machines can generate a pair of numbers that will make her a winner.

---

对于小输入，我们可以检查所有可能的对，但如何对大输入进行检查。我想我们首先将二进制数表示为字符串，然后检查给出的答案小于 K 的排列。但我似乎无法弄清楚如何计算 2 个二进制字符串的可能排列。

Answer 1

我使用了我详细描述的一般 DP 技术 in another answer .

我们要计算 (a, b) 对，使得 a < A, b < B 和 a & b < K。

第一步是将数字转换为二进制并通过添加前导零将它们填充到相同的大小。我只是将它们填充到固定大小 40。这个想法是一点一点地建立有效的 a 和 b。

令 f(i, loA, loB, loK) 为大小为 40 - i 的 a 和 b 的有效后缀对的数量。如果 loA 为真，则意味着直到 i 的前缀已经严格小于 A 的相应前缀。在这种情况下，对 a 的下一个可能位没有限制。如果 loA 为假，则 A[i] 是我们可以放置在当前前缀末尾的下一位的上限。 loB 和 loK 具有类似的含义。

现在我们有以下转换:

long long f(int i, bool loA, bool loB, bool loK) {
  // TODO add memoization
  if (i == 40)
    return loA && loB && loK;
  int hiA = loA ? 1: A[i]-'0';  // upper bound on the next bit in a
  int hiB = loB ? 1: B[i]-'0';  // upper bound on the next bit in b
  int hiK = loK ? 1: K[i]-'0';  // upper bound on the next bit in a & b
  long long res = 0;
  for (int a = 0; a <= hiA; ++a)
    for (int b = 0; b <= hiB; ++b) {
      int k = a & b;
      if (k > hiK) continue;
      res += f(i+1, loA || a < A[i]-'0',
                    loB || b < B[i]-'0',
                    loK || k < K[i]-'0');
    }
  return res;
}

结果是f(0, false, false, false)。

如果添加内存以确保每个子问题只被解决一次，则运行时间为 O(max(log A, log B))。