洛谷P2396 yyy loves Maths VII【状压dp】
题目：https://www.luogu.org/problemnew/show/P2396
题意：有n个数，每次选择一个表示走$a[i]$步，每个数只能选一次。
最多有两个厄运数字，如果走到了厄运数字就不能继续走下去了。
选完所有数有多少种方案。
思路：n很小，状压。
用state表示已经选了哪几个数。如果state是厄运数字就continue
不是的话state就需要加上所有是1的，这道题卡常，所以可以用上lowbit。再开O2优化。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<map> 4 #include<set> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<cmath> 9 #include<stack> 10 #include<queue> 11 #include<iostream> 12 13 #define inf 0x3f3f3f3f 14 #define lowbit(i) i&(-i) 15 using namespace std; 16 typedef long long LL; 17 typedef pair<int, int> pr; 18 19 int n, m; 20 const int maxn = 25; 21 const int mod = 1e9 + 7; 22 int bad[3]; 23 int dp[1 << maxn], dis[1 << maxn]; 24 25 26 int main() 27 { 28 scanf("%d", &n); 29 for(int i = 0; i < n; i++){ 30 scanf("%d", &dis[1 << i]); 31 } 32 scanf("%d", &m); 33 for(int i = 0; i < m; i++){ 34 scanf("%d", &bad[i]); 35 } 36 dp[0] = 1; 37 int mx = 1 << n; 38 for(int i = 1; i < mx; i++){ 39 dis[i] = dis[i ^ lowbit(i)] + dis[lowbit(i)]; 40 if(dis[i] == bad[0] || dis[i] == bad[1])continue; 41 for(int j = i, k = lowbit(j); j; j ^= k, k = lowbit(j)){ 42 dp[i] += dp[i ^ k]; 43 if(dp[i] >= mod)dp[i] -= mod; 44 } 45 } 46 47 printf("%d ", dp[mx - 1]); 48 return 0; 49 }