题目大意： 给一个长度为$n(1\leqslant n\leqslant24)$的序列$S$和$k(0\leqslant k\leqslant2)$个数。 求有多少种$S$的排列方式使得其任何一个前缀和都不是$k$个数里的任意一个。 题解： 状压$DP$，枚
题目大意：给一个长度为$n(1\leqslant n\leqslant24)$的序列$S$和$k(0\leqslant k\leqslant2)$个数。
求有多少种$S$的排列方式使得其任何一个前缀和都不是$k$个数里的任意一个。
题解：状压$DP$，枚举当前选的数的状态和下一个数，卡常，枚举下一个数的时候不可以直接枚举，要枚举$lowbit$看是从哪个数转移过来的，洛谷那道题特别卡常，需要开$O(2)$
卡点：无
C++ Code：
#include <cstdio>
#define maxn 30
#define N (1 << 24 | 5)
const int mod = 1e9 + 7;
int n, k;
int s[maxn], _1, _2;
inline long long fac(int n) {
long long res = 1;
for (int i = 2; i <= n; i++) res = res * i % mod;
return res;
}
int f[N], S[N];
inline void up(int &a, int b) {if ((a += b) >= mod) a -= mod;}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", s + i), S[1 << i - 1] = s[i];
scanf("%d", &k);
if (!k) return !printf("%lld\n", fac(n));
switch (k) {
case 2: scanf("%d", &_2);
case 1: scanf("%d", &_1);
}
int U = 1 << n;
f[0] = 1;
for (register int i = 1; i < U; i++) {
int k = i & -i;
S[i] = S[i ^ k] + S[k];
if (S[i] != _1 && S[i] != _2) for (register int j = i; j; j &= j - 1) up(f[i], f[i ^ (j & -j)]);
}
printf("%d\n", f[U - 1]);
return 0;
}