洛谷P2396 yyy loves Maths VII【状压dp】

题目：https://www.luogu.org/problemnew/show/P2396

题意：有n个数，每次选择一个表示走$a[i]$步，每个数只能选一次。

最多有两个厄运数字，如果走到了厄运数字就不能继续走下去了。

选完所有数有多少种方案。

思路：n很小，状压。

用state表示已经选了哪几个数。如果state是厄运数字就continue

不是的话state就需要加上所有是1的，这道题卡常，所以可以用上lowbit。再开O2优化。

 #include<cstdio>

 #include<cstdlib>

 #include<map>

 #include<set>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<stack>

 #include<queue>

 #include<iostream>

 #define inf 0x3f3f3f3f

 #define lowbit(i) i&(-i)

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> pr;

 int n, m;

 const int maxn = ;

 const int mod = 1e9 + ;

 int bad[];

 int dp[ << maxn], dis[ << maxn];

 int main()

 {

     scanf("%d", &n);

     for(int i = ; i < n; i++){

         scanf("%d", &dis[ << i]);

     }

     scanf("%d", &m);

     for(int i = ; i < m; i++){

         scanf("%d", &bad[i]);

     }

     dp[] = ;

     int mx =  << n;

     for(int i = ; i < mx; i++){

         dis[i] = dis[i ^ lowbit(i)] + dis[lowbit(i)];

         if(dis[i] == bad[] || dis[i] == bad[])continue;

         for(int j = i, k = lowbit(j); j; j ^= k, k = lowbit(j)){

             dp[i] += dp[i ^ k];

             if(dp[i] >= mod)dp[i] -= mod;

         }

     }

     printf("%d\n", dp[mx - ]);

     return ;

 }