P2396 yyy loves Maths VII

Alex_Wei · 2022-10-19 13:46:17 · 题解

P2396 yyy loves Maths VII

双倍经验。

设 f_S 表示集合 S 的答案，若 g_S = \sum_{i\in S} a_i 不合法，则 f_S = 0，否则 f_S = \sum_{i\in S} f_{S\backslash i}。

直接做的时间复杂度为 \mathcal{O}(2 ^ n n)，开 O2 可以通过。我们枚举 i 的时候通过 \mathrm{lowbit}(S) 做到不枚举无用转移，有 \frac 1 2 的常数。

优化：

• 若 k = 0，则答案为 n!。

• 若 k = 1，则答案为 n! - \sum_{g(S) = x} |S|! (n - |S|)!。

• 当 g_S < \min(x, y) 时，f_S = |S|!。可以将 x, y 同时变成 \sum a_i - x, \sum a_i - y 使 \min(x, y) 变大。

• 当使得 g(S) = x 和 g(T) = \sum a_i - y 的 S 和 T 的数量之积不大时，可以枚举 S, T 算出同时经过 x, y 的路径数，再套入 k = 1 的容斥。

代码，不开 O2 获得了最优解（749ms），开 O2 又获得了最优解（476ms）。

怎么没有人写 \boldsymbol {3 ^ {n / 2}} 的做法啊？

设 A(S) 表示集合 S 的 a_i 之和。

考虑 k = 1，我们发现相当于求 n! - \sum\limits_{A(S) = x} |S|! (n - |S|)!。子集和等于某个值，考虑 MITM，将 a 分成两部分 L, R，求出 f_{i, j} 表示 R 的子集 R_1 的数量，使得 |R_1| = i 且 A(R_1) = j。枚举 L 子集 L_1 和 i = |R_1|，则答案减去 f_{i, x - A(L_1)} (i + |L_1|)!(n - i - |L_1|)!。