题解 CF327E 【Axis Walking】

状压dp题，sum[i]为状态为i时的前缀和，dp[i]为到i为止方案数

每次新的状态（sum[i]） = 仅有末尾1的状态 + 去掉末尾1的状态，而二者都在先前求过了，可以O（1）的求出sum[i] 的值

而dp[i] 则要枚举每种情况，用lowbit取1而非枚举每一位来加速，将每种情况累加即可

int N,K,No[2],a[(1<<24)+1];
long long sum[(1<<24)+1],dp[(1<<24)+1];
int lowbit(int Q){
    return Q&(-Q);
}
int main()
{
    N = Read();
    for(int i = 0; i < N; ++i)
    {
        a[i] = Read();
        sum[1<<i] = a[i];
    }
    K = Read();
    for(int i = 0; i < K; ++i)  //个数 <= 2 
        No[i] = Read();
    dp[0] = 1;  
     for(int i = 1; i < (1 << N); ++i)
     {
        sum[i] = sum[i-lowbit(i)] + sum[lowbit(i)];
        if(sum[i] == No[0] || sum[i] == No[1])
            continue;
        for(int j = i; j; j -= lowbit(j))
        {
            dp[i] += dp[i&~lowbit(j)];
            if(dp[i] > Mod) dp[i] -= Mod;
        }
     } 
     cout << dp[(1<<N)-1];
    return 0;
}