「EZEC-10」Equalization 题解

· · 题解

定义

下文中 “A 状态” 表示满足所有数之和为 0 的状态，“A 子集” 同理；“B 状态” 表示某最优方案中，去除所有 “A 状态” 后剩余的那个状态。

求最少操作次数

对于静态区间加，我们很容易想到对数列的差分数组进行操作。

令 d_i 表示 a_{i+1}-a_i\ (i=1,2,...,n-1)。

那么可将每次操作转化为：

\begin{cases}d_r:=d_r-x&l=1\\d_{l-1}:=d_{l-1}+x&r=n\\d_{l-1}:=d_{l-1}+x,d_r:=d_r-x&l\ne 1\ \text{and}\ r\ne n\end{cases}

换句话来说，就是每次你可以进行如下两种操作的其中一种：

而根据题目，我们要将 d 数组全变为 0。

不难发现，若每次都进行第一种操作，次数最多为 n-1。

观察可得，当 d 中某个数为 0 或者某些数之和为 0 时，我们可以省去一次操作。

这样，我们的目标就是将 d 数组尽可能多地划分为和为 0 的组。

考虑状压。

令 f_i 表示 A 状态为 i 时，可恰好划分成和为 0 的最大组数。

对所有 A 状态 i，将 f_i 初始化为 1。

我们对所有 i 的 A 子集 j 进行如下转移：

f_i=\max(f_i,f_j+f_{i\ \text{xor} \ j})

答案即为 n-1-\max\limits^{2^{n-1}-1}_{i=1} {f_i}。

时间复杂度为 O(3^{n-1})。

求方案数

我们只需计算本质不同的方案数，最后乘上最少操作次数的阶乘即可。

先考虑 A 状态。

令 g_i 表示 A 状态为 i 时，本质不同的方案数。

令 bit_i 表示 A 状态为 i 中数的个数。

对于 A 状态 i，若不考虑进一步划分，我们发现对 i 中所有数进行第二种操作时最优。

在 i 中，选定某个非 0 的数 x 后，再选择另一个非 0 的数 y，将 x 变为 0，y 变为 y+x；……

如此重复进行下去，最终所有数均会变为 0。

此时，本质不同的方案数即为 bit_i 点有标号树计数。（对于每个非根节点，其自身作为 x，其父节点作为 y。）

根据 prufer 序列可推得，方案数为 bit_i^{bit_i-2}。

故我们对所有 A 状态 i，将 g_i 初始化为 bit_i^{bit_i-2}。

在更新 f 数组时，可同时更新 g 数组。

我们对所有 i 的 A 子集 j 进行如下转移：

\begin{cases}g_i:=g_i+g_j\times g_{i\ \text{xor} \ j}&f_i=f_j+f_{i\ \text{xor} \ j}\\g_i:=g_j\times g_{i\ \text{xor} \ j}&f_i<f_j+f_{i\ \text{xor} \ j}\end{cases}

而这样转移可能会重复计算。

故考虑只枚举不包含任何 A 子集的 j。

当然，每枚举一个 j，就要对所有 i\ \text{xor}\ j 的子集进行标记，之后也就不会再枚举到 i\ \text{xor}\ j 的子集了。

这样我们就成功避免了重复计算的问题。

再考虑 B 状态。

令 c_i 表示 B 状态为 i 时，本质不同的方案数。

不难发现，B 状态中所有数之和与 a_1-a_n 相加恰为 0。

故将 B 状态再加入 a_1-a_n 即可变为 A 状态。

沿用处理 A 状态的思路，而注意，当选中的 x 或 y 中有一个是 a_1-a_n 时，就会存在两种可能的情况。

故在进行计算时，可以考虑将 a_1-a_n 看作一个含两个点的连通块。

根据 prufer 序列可推得，c_i=2\times (bit_i+2)^{bit_i-1}。

最后枚举所有能达到最少操作次数的状态。

易得满足条件的状态 i 贡献为 g_i\times c_{n-1-bit_i}。

将所有状态的贡献相加求和，再乘上最少操作次数的阶乘即为最终答案。

注意特判 f 数组均为 0 的情况，此时的答案为 c_{n-1} 乘上最少操作次数的阶乘。

时间复杂度仍为 O(3^{n-1})。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,cnt,ans1,ans2,a[18],d[18],c[18],fact[18],power[18],f[1 << 17],g[1 << 17],v[1 << 17],val[1 << 17],bit[1 << 17],mod = 1e9 + 7;
inline ll read(){
   ll s = 0,w = 1;
   char ch = getchar();
   while (ch < '0'|| ch > '9'){ if (ch == '-') w = -1; ch = getchar();}
   while (ch >= '0'&& ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
   return s * w;
}
ll qp(ll x,ll y){
    ll a = 1,b = x;
    while (y){
        if (y & 1) a = a * b % mod;
        b = b * b % mod,y >>= 1;
    }
    return a;
}
int main(){
    n = read();
    for (ll i = 0;i < n;i += 1) a[i] = read();
    n -= 1;
    for (ll i = 0;i < n;i += 1) d[i] = a[i + 1] - a[i];
    c[0] = fact[0] = power[1] = 1;
    for (ll i = 1;i <= n;i += 1) fact[i] = fact[i - 1] * i % mod;
    for (ll i = 2;i <= n;i += 1) power[i] = qp(i,i - 2);
    for (ll i = 1;i <= n + 1;i += 1) c[i] = 2 * qp(i + 2,i - 1) % mod;
    for (ll i = 1;i < (1 << n);i += 1){
        ll sum = 0;
        for (ll j = 0;j < n;j += 1) if (i & (1 << j)) sum += d[j],bit[i] += 1;
        if (!sum) f[i] = 1,g[i] = power[bit[i]];
    }
    for (ll i = 1;i < (1 << n);i += 1) if (f[i]){
        bool fl = 1;
        for (ll j = (i - 1) & i;j;j = (j - 1) & i) if (f[j]){fl = 0; break;}
        val[i] = fl;
    }
    for (ll i = 1;i < (1 << n);i += 1) if (f[i]){
        for (ll j = i;j;j = (j - 1) & i) v[j] = 0;
        for (ll j = (i - 1) & i;j;j = (j - 1) & i) if (val[j] && !v[j]){
            if (f[j] + f[i ^ j] > f[i]) f[i] = f[j] + f[i ^ j],g[i] = g[j] * g[i ^ j] % mod;
            else if (f[j] + f[i ^ j] == f[i]) g[i] = (g[i] + g[j] * g[i ^ j] % mod) % mod;
            for (ll k = (i ^ j);k;k = (k - 1) & (i ^ j)) v[k] = 1;
        }
    }
    ans1 = n - *max_element(f,f + (1 << n));
    if (ans1 == n){cout<<n<<endl<<c[n] * fact[ans1] % mod; return 0;}
    for (ll i = 0;i < (1 << n);i += 1) if (f[i] == n - ans1) ans2 = (ans2 + g[i] * c[n - bit[i]] % mod) % mod;
    cout<<ans1<<endl<<ans2 * fact[ans1] % mod;
    return 0;
}