题解：P7718 「EZEC-10」Equalization

_Communist · 2025-11-26 14:49:05 · 题解

竞选最 tang 做法。O(3^n) 可以看其它题解，这里主要讲用集幂做到 O(2^nn^2)。

首先 O(3^n) 是很简单的。令 dp_S 为集合 S 的 (最小代价，方案数)，转移是类似 \exp 状物。考虑这东西不弱于集合幂级数 \exp，数据范围又这么大，优化只有可能是 O(2^nn^2)。

直接套 \exp 板子会有一个问题：由于需要同时记录两个问的答案，虽然加法和乘法容易重定义，但 IFWT 的减法不好处理。如果强行支持减法，需要一个 O(n) 的代价（需要记录所有可能的最优值与方案数），对时空都是难以接受的。

既然这个第一问阻碍了无脑套 \exp 板子，那就先把它解决掉。最优性问题不需要记录那么多信息，做到 O(2^nn) 是简单的，可以求出每个集合内部的最小代价。

再考虑第二问，为了在满足第一问的条件下计数。

假设已经知道了 f_S 表示集合 S 划分为尽可能多的和为 0 的集合的方案数，由广义 Cayley 定理，对于一个极大的 S 其对答案的贡献为 f_S\times 2(n-|S|+2)^{n-|S|-1}（这里 n 其实是原题面的 n-1）。

至于如何求 f_S，这里有两个做法：

• 设最优方案中选了 c 个和为 0 的集合，再令 F_S=|S|^{|S|-2} 当且仅当 S 和为 0，则相当于求 F^c（这里集合幂级数之间乘法为子集卷积）。

• 延续 \exp 的思路，令 F_S=|S|^{|S|-2} 当且仅当 S 和为 0 且 S 极小，则 f=\exp F。极小的意思是不存在 T\subsetneqq S 满足 T 和为 0，如果存在的话 S 必然不会在最优解里面。

第一种做法常数应该很大，代码实现了第二种做法，常数稍微小一点。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using LL = unsigned long long;
constexpr int MAXN = 22, mod = 1e9 + 7, INF = 1e9;
inline void inc(int &x, int y) { (x += y) >= mod && (x -= mod); }
inline void dec(int &x, int y) { (x -= y) < 0 && (x += mod); }
inline int qpow(int x, int y = mod - 2) {
    int ret = 1;
    while (y) {
        if (y & 1) ret = (LL)ret * x % mod;
        x = (LL)x * x % mod, y >>= 1;
    }
    return ret;
}
int n, inv[MAXN + 1], cl[MAXN + 1], excl[MAXN + 1], popc[1 << MAXN];
long long a[MAXN + 1], s[1 << MAXN];
int f[1 << MAXN], dp[1 << MAXN], F[MAXN + 1][1 << MAXN], G[MAXN + 1][1 << MAXN];
inline void FMT(int *f) { for (int i = 0; i < n; ++i) for (int S = 0; S < (1 << n); ++S) if ((S >> i) & 1) inc(f[S], f[S ^ (1 << i)]); }
inline void IFMT(int *f) { for (int i = 0; i < n; ++i) for (int S = 0; S < (1 << n); ++S) if ((S >> i) & 1) dec(f[S], f[S ^ (1 << i)]); }
inline void exp() {
    for (int S = 0; S < (1 << n); ++S) F[popc[S]][S] = dp[S];
    for (int i = 0; i <= n; ++i) FMT(F[i]);
    for (int i = 0; i <= n; ++i) for (int S = 0; S < (1 << n); ++S) G[i][S] = (LL)F[i][S] * i % mod;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            for (int S = 0; S < (1 << n); ++S) inc(G[i][S], (LL)G[j][S] * F[i - j][S] % mod * (i - j) % mod);
        }
        for (int S = 0; S < (1 << n); ++S) G[i][S] = (LL)G[i][S] * inv[i] % mod;
    }
    for (int i = 0; i <= n; ++i) IFMT(G[i]);
    for (int S = 0; S < (1 << n); ++S) dp[S] = G[popc[S]][S];
}
inline void init() {
    for (int i = 1; i <= n; ++i) inv[i] = qpow(i);
    cl[0] = cl[1] = 1;
    for (int i = 2; i <= n; ++i) cl[i] = qpow(i, i - 2);
    excl[0] = 1;
    for (int i = 1; i <= n; ++i) excl[i] = (LL)qpow(i + 2, i - 1) % mod * 2 % mod;
    for (int S = 1; S < (1 << n); ++S) s[S] = s[S ^ (S & -S)] + a[__builtin_ctz(S)], popc[S] = __builtin_popcount(S);
}
int main() {
    IOS;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    --n;
    for (int i = 0; i < n; ++i) a[i] = a[i + 1] - a[i];
    init();
    fill(f + 1, f + (1 << n), INF);
    for (int S = 0; S < (1 << n); ++S) {
        for (int i = 0; i < n; ++i) if ((S >> i) & 1) f[S] = min(f[S], f[S ^ (1 << i)] + bool(s[S]));
    }
    cout << f[(1 << n) - 1] << '\n';
    for (int S = 0; S < (1 << n); ++S) if (!s[S] && f[S] == popc[S] - 1 && f[((1 << n) - 1) ^ S] + f[S] == f[(1 << n) - 1]) dp[S] = cl[popc[S]];
    exp();
    dp[0] = 1;
    int ans = 0;
    for (int S = 0; S < (1 << n); ++S) if (!s[S] && f[S] + n - popc[S] == f[(1 << n) - 1]) {
        inc(ans, (LL)dp[S] * excl[n - popc[S]] % mod);
    }
    for (int i = 1; i <= f[(1 << n) - 1]; ++i) ans = (LL)ans * i % mod;
    cout << ans << '\n';
    return 0;
}