CF327E Axis Walking

题目传送门

一、题目大意

给你一个长度为\(n\)(\(1<=n<=24\))的正整数序列\(S\)，再有\(k\)(\(0<=k<=2\))个正整数。

求有多少种\(S\)的排列方式使得其任意前缀和不会成为那\(k\)个数里的任意一个。 答案对\(1e9+7\)取模。

二、题目解析

这题很明了，一看就是状压\(dp\)

对于那些前缀和我们可以累加取得

不妨设\(sum[i]\)表示当状态为\(i\)时的前缀和

那么显然有\(sum[i]=∑i\)中为\(1\)的位置的\(sum\)

对于那些\(sum[i]\)为给定的数的状态显然要舍去

那么不妨再设\(f[i]\)为状态为\(i\)时的方案数

类似于\(sum\)的转移，显然有\(f[i]=∑i\)中为\(1\)的位置的\(f\)
发现这两者都需要访问那些状态\(i\)中的\(1\)的位置

那么对于这些状态\(i\)中那些为\(1\)的位置如何访问呢？

我们当然不能每次都让\(i>>1\)然后再判断这一位是否为\(1\)，因为这样太慢了

所以我们需要快速地访问那些\(1\)的位置

这时需要用到神奇（毒瘤）的位运算了

我们发现当\(i \& \sim lowbit(i)\)时恰好能达到这一点

它相当于把\(i\)最低位\(1\)以后的部分全部消去了，相当于加速了我们的查找过程

于是乎，这题就与普通的状压\(dp\)无异了

三、完整代码

#include 

using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;        //取模
const int N = 1 << 24;          //最多24个数字
int n;                          //实际n个数字
int k;                          //k个不允许出现的数字
int full;                       //将所有位置全部为1时的拉满状态，对应的十进制数
unordered_set no_permit;   //有哪些数字是不允许出现在前缀和中的
int f[N];                       //f[i]表示状态为i时的方案数
LL sum[N];                      //sum[i]表示当状态为i时的前缀和

//一般状态压缩DP，n<=12,这里的n<=24，看来暴力的状态压缩要挂~
int lowbit(int x) {
    return x & (-x);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> sum[1 << i]; //按二进制位置映射的十进制数来存储(状态压缩式的存储方法)
    //前缀和不允许出现的数字
    cin >> k;
    int x;
    for (int i = 0; i < k; i++)cin >> x, no_permit.insert(x);

    //状态为0时，表示一个全部都不选择，那么前缀和是0，肯定不在给定的k个正整数之中。因为正整数都大于0，这是一种唯一方案。
    f[0] = 1, full = (1 << n) - 1;//满状态
    //枚举现在的状态
    for (int i = 1; i <= full; i++) {
        //每次新的状态（sum[i]） = 仅有末尾1的状态 + 去掉末尾1的状态，而二者都在先前求过了，可以O(1)的求出sum[i] 的值
        sum[i] = sum[i & ~lowbit(i)] + sum[lowbit(i)];
        //sum[i] += sum[i - 1]; 这种传统方法是不可以的，因为sum数组并不是按一个个数字按次序保存的，而是按二进制数位方式保存的
        //这所以这样保存，是因为状态压缩DP，是需要枚举每一个数位，每个数位与传统方式的前缀和不符，需要特殊记忆一下这个方法
        //如果前缀和等于限定的数，那么是不合法的
        if (no_permit.count(sum[i]))continue;

        //快速找到所有位置为1的
        for (int j = i; j; j -= lowbit(j))//枚举可能的上一次状态
            f[i] = (f[i] + f[i & ~lowbit(j)]) % MOD; //去掉j位为1的 i & ~lowbit(j)
    }
    printf("%d\n", f[full]);
    return 0;
}