数位动态规划中从高位到低位和从低位到高位的区别

题解

求满足以下条件的$(x,y)$整数对数：（适用高位到低位$DP$）

1. $x∈[0,A],y∈[0,B]$

2. $x xor y≤W$

求满足以下条件的$(x,y)$整数对数：（适用低位到高位$DP$）

1. $x∈[0,A],y∈[0,B]$

2. $x xor y ≤ W$

3. $x - y ≤ K$

大多数情况下，从高位到低位进行$DP$都更为便捷。但第二道例题中有加法（也可以看作减法），也就是有进位（也可以看作有借位），此时从低位到高位显然更便捷。

对于第二道例题：设$f[bit][xA][yB][xKy][yKx][xyw][cxK][cyK]$表示在已确定最低的$bit$位的情况下，是否有$x ≤ A$，是否有$y ≤ B$，是否有$x + K ≤ y$，是否有$y + K ≤ x$，是否有$x xor y ≤ W$，$x + K$是否产生了进位，$y + K$是否产生了进位时的答案。