动态规划+位掩码

Question

我最近学习了竞争性编程的位操作概念，所以我对这个概念很陌生，我也阅读了很多关于位掩码的教程+ 动态编程 上 Hackerearth、CodeChef 等等。

我还在 Codechef 上解决了几个问题，包括这个 problem 在我回答了一些问题之后，我对位掩码有一些疑问。

我解决的问题主要集中在操纵子集但我想知道我如何使用位掩码处理 permutations ，即什么时候我必须在需要设置掩码中所有位的状态下工作。

例如：如果我们必须找到可以通过排列给定数字 A 的所有数字组成的数字的数量，这些数字可以被给定数字 B 整除，其中 (A ,B<= 10**6) 如何这可以用位掩码来完成吗？（我希望这可以用位掩码+dp来完成）

如果 A=514，且 B=2 该问题期望答案为

514

154

它们都可以被 2 整除。

所以答案是2。据我了解：514 和 154 代表相同的掩码 111，其中所有位都是 set 那么我如何在掩码所在的位置使用位掩码两个或更多答案相同！（我希望你明白这一点）。

而且由于我们可以有那么多的数字排列，所以不可能为 n!*n 的值分配价值 n!*n 的内存，所以如何使用我们只需要 (2*) 的位掩码来解决这个问题*n)*n space （如果我没记错的话）。

那么如何迭代地解决上述问题呢？ /或我可能理解的任何 DP 状态方程，我无法理解我读过的一些类似问题的递归方法。

我也想过类似的问题TSHIRTS，但我无法理解递归背后的逻辑。

Answer 1

你实际上不需要 DP，但你可以很好地使用位操作 :) 因为 A <= 10^6 这意味着 A 最多有 7 个数字；所以你只需要检查7！ = 5040 个州。

const int A = 514;
const int B = 2;
vector <int> v; //contains digits of A (e.g. 5, 1, 4) this can be done before the recursive function in a while loop.

int rec(int mask, int current_number){
    if(mask == (1 << v.size()) - 1){ //no digit left to pick
        if(current_number % B == 0) return 1;
        else return 0;
    }
    int ret = 0;
    for(int i = 0; i < v.size(); i++){
        if(mask & (1 << i)) continue; //this is already picked
        ret += rec(mask | (1 << i), current_number * 10 + v[i]);
    }
    return ret;
}

注意我这里没有使用DP的原因是即使掩码相同，当前数字也可能不同；所以你实际上不能说这种情况已经重复了。除非你记住掩码 AND current_number 这需要更多 space.

动态规划+位掩码

Dynamic Programming +Bit-Masks

algorithm

bitmask

dynamic-programming