题解 P7718 「EZEC-10」Equalization

· · 题解

洛谷题面传送门

一道挺有意思的题，现场切掉还是挺有成就感的。

首先看到区间操作我们可以想到差分转换，将区间操作转化为差分序列上的一个或两个单点操作，具体来说我们设 b_i=a_{i+1}-a_i，那么对于一次形如 \forall i\in[l,r],a_i\leftarrow a_i+x 的操作三元组 (l,r,x)，我们有：

于是问题转化为：给定长度为 n-1 的差分序列，每次可以进行以下两种操作之一：修改一个单点的值，或者指定三个整数 x,y,z，将 b_x 改为 b_x+z，b_y 改为 b_y-z，最少需要多少次操作才能将所有数变为 0。

直接处理不太容易，因此考虑挖掘一些性质。做过这道题的同学应该不难想到，我们可以在每次操作的两个点之间连一条边，如果咱们操作的是一个单点那么就连一条自环，这样显然会得到一张点数为 n-1，边数等于操作次数的图。那么有一个性质：在最优策略连出的图中，对于每个连通块 (V',E')，记 S=\sum\limits_{x\in V'}b_x，有

证明不会，感性理解一下即可

观察到这个性质之后，求解第一问就易如反掌了，注意到 n 很小，因此考虑状压，记 dp_S 表示将 S 中的元素变为 0 的最少操作次数，枚举子集转移即可，复杂度 3^{n-1}。

接下来考虑第二问，显然每次操作都是不同的，因此我们可以只用考虑操作方案的集合有哪些，最后乘个操作次数的阶乘即可。其次，如果我们能够知道对于一个连通块而言，将它按照最优策略变为 0 的方案数，我们就能用乘法原理一边 DP 一遍记录将每个集合变为 0 的最优策略的方案数了。因此考虑将每个集合变为 0 的方案数，还是分 S=0 和 S\ne 0 两种情况处理：

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

using namespace fastio;
const int MAXN=18;
const int MAXP=1<<17;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
int n,a[MAXN+3],b[MAXN+3],m=0,c[MAXN+3],cnt[MAXP+5],fac[MAXN+5];
int f[MAXN+5],g[MAXN+5];
ll sum[MAXP+5];pii dp[MAXP+5];
inline int high(int x){return (!x)?-1:(31-__builtin_clz(x));}
int qpow(int x,int e){
    int ret=1;
    for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
    return ret;
}
void upd(pii &x,pii y,int v,int z){
    return (x.fi<y.fi+v)?void():(((x.fi==y.fi+v)?(x.se=(x.se+1ll*y.se*z)%MOD):
    (x.fi=y.fi+v,x.se=1ll*y.se*z%MOD)),void());
}
int main(){
    scanf("%d",&n);dp[0]=mp(0,1);
    for(int i=(fac[0]=1);i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD;
    for(int i=2;i<=n;i++) g[i]=qpow(i,i-2),f[i]=2ll*g[i]*i%MOD;f[1]=2;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<n;i++) b[i]=a[i+1]-a[i];
    for(int i=1;i<n;i++) if(b[i]) c[++m]=b[i];
    for(int i=1;i<(1<<m);i++) dp[i].fi=INF;
    for(int i=1;i<(1<<m);i++){
        int pos=32-__builtin_clz(i&(-i));
        sum[i]=sum[i&(i-1)]+c[pos];
        cnt[i]=cnt[i&(i-1)]+1;
    }
    for(register int i=0;i<(1<<m);i++){
        register int rst=((1<<m)-1)^i;
        for(register int j=rst;j;j=(j-1)&rst){
            if(high(j)<high(i)) break;
            (!sum[j])?upd(dp[i|j],dp[i],cnt[j]-1,g[cnt[j]]):
            upd(dp[i|j],dp[i],cnt[j],f[cnt[j]]);
        }
    } printf("%d\n%d\n",dp[(1<<m)-1].fi,1ll*dp[(1<<m)-1].se*fac[dp[(1<<m)-1].fi]%MOD);
    return 0;
}