Axis Walking
题目描述
给你一个长度为 \(n(1\le n\le 24)\) 的正整数序列 \(S\)，再有 \(k(0\le k\le 2)\) 个正整数。
求有多少种 \(S\) 的排列方式使得其前缀和不会成为那 \(k\) 个数里的任意一个。
答案对 \(10^9+7\) 取模。
Solution
挺简单的一个状压 DP。
考虑 \(f(S)\) 表示当前选数集合为 \(S\) 的方案数，那么显然当前集合固定为 \(S\) 的时候且下一个选的数为 \(x\) 的时候，只需要保证 \(x+\displaystyle\sum\limits_{v\in S}v\) 不等于给定的 \(k\) 个值即可。
对于 \(\displaystyle\sum\limits_{v\in S}v\) 可以提前 \(\mathcal O(n2^n)\) 预处理。转移的话是枚举子集的 \(\mathcal O(n3^n)\)，常数非常小。
Code
int N, K, A[_N], B[2];
mint f[_M];
i64 val[_M];
inline int lowbit(int x) {return x & -x;}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
For(i, 1, N) cin >> A[i];
cin >> K;
For(i, 1, K) cin >> B[i];
f[0] = 1, val[0] = 0;
int lim = 1 << N;
For(S, 1, lim - 1) {
val[S] = val[S^lowbit(S)] + A[__builtin_ctz(S)+1];
if (val[S] == B[1] || val[S] == B[2]) continue;
for (int t = S; t; t ^= lowbit(t))
f[S] += f[S^lowbit(t)];
}
cout << f[lim-1] << '\n';
}