题意:给定一个长度为n的数组a,再给定k个数,要求重新排列数组a,使得不存在任意一个前缀和等于k个数中的任意一个数,求方案数。
解法:状态压缩DP,优化
这个状压的想法好想
状态设计:$dp[i]$ 表示选数状态为i的时候的方案数
状态转移:设 $sum[i]$ 表示状态为i时候的数的和,当 $sum[i]$ 不在k个数中时,则有 $dp[i] += dp[T]$ 其中 $i \,xor \,j = 2^p$
所以得到代码
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
int n; cin >> n;
int ed = 1 << n;
vector<int> a(1 << n);
for (int i = 0; i < n; i ++ ) cin >> a[i];
vector<LL> sum(1 << n), t(2, 0);
for (int i = 0; i < ed; i ++ ) {
for (int j = 0; j < n; j ++ ) if (i >> j & 1) sum[i] += a[j];
}
int k; cin >> k;
for (int i = 0; i < k; i ++ ) cin >> t[i];
vector<LL> dp(1 << n);
dp[0] = 1;
for (int i = 1; i < ed; i ++ ) {
if (sum[i] == t[0] || sum[i] == t[1]) continue;
for (int j = 0; j < n; j ++ ) {
if (i >> j & 1) {
int last = i ^ (1 << j);
dp[i] = (dp[i] + dp[last]) % MOD;
}
}
}
cout << dp[ed - 1] << endl;
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
// int T; cin >> T;
// while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
可惜会T
考虑优化,利用lowbit
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
LL a[1 << 24], dp[1 << 24];
int t[2];
inline void solve() {
int n; cin >> n;
int ed = 1 << n;
for (int i = 1; i < ed; i <<= 1) cin >> a[i];
int k; cin >> k;
for (int i = 0; i < k; i ++ ) cin >> t[i];
dp[0] = 1;
for (int i = 1; i < ed; i ++ ) {
a[i] = a[i ^ lowbit(i)] + a[lowbit(i)];
if (a[i] == t[0] || a[i] == t[1]) continue;
for (int j = i; j; j -= lowbit(j)) dp[i] = (dp[i] + dp[i ^ lowbit(j)]) % MOD;
}
cout << dp[ed - 1] << endl;
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
// int T; cin >> T;
// while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}