USACO22Feb Redistributing Gifts G 题解
balabala...
动态规划 状态压缩
感觉是这次 USACO Gold 里面最有意思也是最难的题目，不过还好，在这个题上花了 \(1.5\) 小时终于 AK 晋级了。
不难想出 \(\mathcal O(3^nn^2)\) 的暴力：
对于每个集合 \(s\)，预处理出钦定这些奶牛同色的方案数 \(g(s)\)，设 \(U\) 代表全集，那么每次的答案就是两种颜色的奶牛的方案的拼接： \(g(s)g(U/s)\)。
\(g(s)\) 可以通过记 \(f(s, lst)\) 表示当前被占用的物品的集合为 \(s\)，然后上一个物品为 \(lst\) 的方案数得出。
复杂度就是所有状态的子集个数 \(\times\) \(n^2\)。
然后我们发现这中每次枚举一个集合 \(s\)，然后跑一遍比较浪费，同时又注意到假如我们对于每个 \(i\)，假设它选了物品 \(p_i\)，那么就连一条边 \((i, p_i)\)，然后我们发现我们每次枚举 \(s\)，实际上就是将整个集合划分成若干个置换环，于是我们可以先求出 \(g(s)\) 表示将 \(s\) 连成一个置换环的方案数，\(h(s)\) 表示将 \(s\) 分成若干置换环的方案数。
记 \(x\) 为 \(s\) 中的一个任意元素（我们枚举这个元素所在置换环的方案，方便起见，可以取 \(\log_2 \mathrm{lowbit}(s)\)），那么 \(h(s)\) 的转移显然：
\[h(s) = \sum_{s' \subseteq s, x \in s'} g(s') h(s / s') \]这个的复杂度就是 \(3^n\)，可以承受。
于是重点就是求解 \(g(s)\)。
第一眼，可以有一个略微暴力的想法，记 \(f(s, st, ed)\) 表示当前 \(s\) 这个集合中的物品已经被占用了，整个置换环的起始点是 \(st\)，目前上一个元素是 \(ed\)，每次转移的时候枚举下一个元素 \(i\)，然后只要 \(i\) 没有被占用且 \(ed\) 选 \(i\) 合法后就可以转移了。特别地，如果 \(i = st\)，那么就形成环了，于是 \(g(s \cup \{i\}) \gets g(s \cup \{i\}) + f(s, st, ed)\)。
最后，每一个置换环都被算了环长遍，于是将 \(g(s)\) 除以环长即可。
具体可以看代码：
#define in read()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)
using namespace std;
using ll = long long;
template < typename T > T read() {
T x = 0; bool f = 0; char ch = getchar();
while(!isdigit(ch)) f |= ch == '-', ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
const int N = (1 << 16) + 10;
ll f[N][17][17], g[N], h[N];
int n, Q;
char s[20];
int p[20][20];
bool avi[20][20];
int lg[N];
int main() {
n = in;
rep(i, 0, n - 1) {
rep(j, 0, n - 1) p[i][j] = in - 1;
rep(j, 0, n - 1) {
avi[i][p[i][j]] = true;
if(p[i][j] == i) break;
}
} int U = 1 << n; U--;
rep(i, 0, n - 1) f[0][i][i] = 1;
rep(s, 0, U)
rep(st, 0, n - 1) if(~s >> st & 1)
rep(ed, 0, n - 1) if(ed == st || s >> ed & 1) if(f[s][st][ed]) {
rep(i, 0, n - 1)
if(~s >> i & 1 && avi[ed][i]) {
if(i == st) g[s | 1 << st] += f[s][st][ed];
else f[s | 1 << i][st][i] += f[s][st][ed];
}
}
rep(i, 2, U) lg[i] = lg[i >> 1] + 1; h[0] = 1;
rep(s, 1, U) g[s] /= __builtin_popcount(s);
rep(s, 1, U) {
int x = lg[s & -s];
for(int t = s; t; t = (t - 1) & s) if(t >> x & 1)
h[s] = h[s] + g[t] * h[s ^ t];
}
Q = in;
while(Q--) {
scanf("%s", s);
int stu = 0; rep(i, 0, n - 1) if(s[i] == 'H') stu |= 1 << i;
ll ans = h[stu] * h[U ^ stu];
printf("%lld\n", ans);
}
return 0;
}
只要把这个代码交上去，就可以通过 \(12 / 18\) 的测试点，瓶颈在于空间，如果要强行卡空间，应该可以通过 \(n = 17\)。
考虑继续优化，我们的瓶颈仍然在于 \(f(s, st, ed)\) 上面，如果我们能够删除一维状态，那么就可以完美地通过所有测试点了！
\(ed\) 是显然很必要的，但是 \(st\)，我们可以观察它在 DP 中的作用：
- 判断什么时候形成置换环。
感觉这个作用比较垃圾，于是我们可以钦定一个置换环中，编号最小的作为 \(st\)，然后只要我们枚举的 \(i\) 是编号最小的点，那么就可以确定形成置换环了！
于是复杂度降为了 \(\mathcal O(2^n n^2 + 3^n)\)，USACO 评测机下，大概每个点 900ms 多。
#include
#define in read()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)
using namespace std;
using ll = long long;
template < typename T > T read() {
T x = 0; bool f = 0; char ch = getchar();
while(!isdigit(ch)) f |= ch == '-', ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
const int N = (1 << 18) + 10;
ll f[N][19], g[N], h[N];
int n, Q;
char s[20];
int p[20][20];
bool avi[20][20];
int lg[N];
int main() {
n = in;
rep(i, 0, n - 1) {
rep(j, 0, n - 1) p[i][j] = in - 1;
rep(j, 0, n - 1) {
avi[i][p[i][j]] = true;
if(p[i][j] == i) break;
}
} int U = 1 << n; U--;
rep(i, 0, n - 1) f[1 << i][i] = 1;
rep(i, 2, U) lg[i] = lg[i >> 1] + 1;
rep(s, 1, U)
rep(ed, 0, n - 1) if(f[s][ed]) {
int x = lg[s & -s];
rep(i, x, n - 1) {
if(i == x && avi[ed][i]) g[s] += f[s][ed];
if(~s >> i & 1 && avi[ed][i])
f[s | 1 << i][i] += f[s][ed];
}
}
h[0] = 1;
rep(s, 1, U) {
int x = lg[s & -s];
for(int t = s; t; t = (t - 1) & s) if(t >> x & 1)
h[s] = h[s] + g[t] * h[s ^ t];
}
Q = in;
while(Q--) {
scanf("%s", s);
int stu = 0; rep(i, 0, n - 1) if(s[i] == 'H') stu |= 1 << i;
ll ans = h[stu] * h[U ^ stu];
printf("%lld\n", ans);
}
return 0;
}