algorithm - 计算具有以下约束的三元组

Question

给定 A、B、C 和 D，我们需要找到满足 ((x xor y) 或 z ) ≤ D 的三元组 (x,y,z) 的数量，条件是 x≤A,y≤B， z≤C 其中A、B、C、D各可达10^18。

由于答案可能非常大，我们需要输出对 10^9+7 取模的三元组数。

基本且低效的方法:

i=0,j=0,k=0,ans=0

FOR (i<=A)

   FOR(j<=B)

     FOR(k<=C)

        if(((i^j)|k)<=D) ans=ans+1

print ans%1000000007

显然它的效率非常低，他们可以有更好的方法吗？

Answer 1

我们可以通过将数字 (x, y, z) 分解成位来解决问题。因为 x, y, z <= 10^18，所以每个数字少于 50 位。

所以从第一位到第50位，我们需要知道四件事

• x是否小于A
• y是否小于B
• z是否小于C
• 是否 (x ^ y) | z 小于 D

所以，我们有我们的功能:

long totalNumber(int bit, boolean lessThanA, boolean lessThanB, boolean lessThanC, boolean lessThanD)

对于每个位的位置，我们只需要为每个数字 x、y、z 尝试位 0 和位 1

    long result = 0;
    for(int x = 0; x < 2; x++){
       for(int y = 0; y < 2; y++){
          for(int z = 0; z < 2; z++){
             //update lessThanA, lessThanB, lessThanC, lessThanD. This step is omitted.
             result += totalNumber(bit + 1, lessThanA, lessThanB, lessThanC, lessThanD);
             result %= MOD; //remember to take modulo of the result. 
          }
       } 
    }

对于我们的基本情况，如果我们到达第 50 位就返回 1

if(bit == 50)
   return 1;

因此，在这种情况下应用动态规划，我们有一个表

dp[位][lessThanA][lessThanB][lessThanC][lessThanD]

时间复杂度将降低到 O(bit * lessThanA * lessThanB *lessThanC * lessThanD) 也就是 ~ O(50*2^4) = O(800)

最后的说明:这种类型的问题在当今的编程竞赛中经常出现。看看problem B round 1B Google Code Jam 2014举个例子。