CF1726G A Certain Magical Party 题解

eastcloud · 2024-11-12 20:02:29 · 题解

很朴素的性质题。

由于每个数经过一次操作后变成的值都是一样的，而若是知道了这个数，我们便能够对序列合法的条件有更清晰的考察，因此先考虑钦定最后的结果为 H，由于每个数操作后不降，因此 H 必定大于等于最大值。

接着我们尝试考虑每个数能够被操作到 H 的条件，我们设每个人的参数为 (a_i,b_i)，不难得到以下条件：

• 当 a_i=H 时，如果 b_i=0，那么我们必须将其排在序列末尾；如果 b_i=1，则把他放在序列的任何一个位置都可以。

• 当 a_i \neq H 时，对于 b_i=0 的人，我们此时要求他的后面必须恰好有 H-a_i 个比他小的人，剩下的人则不作要求；而对于 b_i=1 的人，考虑每个人的贡献不难得到他的后面必须恰好有 (n-1)-(H-a_i) 个大于等于他的人。

由上，如果我们确定了 H，那么计算方案是简单的：只需从小往大逐个插入，每次插入的方案数很好计算，这里不多赘述。

那如何求出 H 呢？最大值最小值相等的情况是显然的，否则考虑一定存在一个最小值 m 最终变成 m+n-1，因此 H 也是唯一确定的，简单模拟即可，可能细节较多，注意判断无解的情况。

int main(){
    int n=read(),maxn=0,minn=2*n+1;init();
    for(int i=1;i<=n;i++)a[i]=read(),maxn=max(maxn,a[i]),minn=min(minn,a[i]);
    for(int i=1;i<=n;i++)b[i]=read(),c[a[i]][b[i]]++;
    if(maxn==minn){write(fac[n]);return 0;}
    int goal=minn+n-1;
    if(maxn>goal){write(0);return 0;}
    int cnt=0,res=1;
    for(int i=minn;i<=maxn;i++){
        int suff=goal-i;
        if(c[i][0] && cnt<suff){write(0);return 0;}
        cnt+=c[i][0];res=mul(res,fac[c[i][0]]);
        if(!c[i][1])continue;
        if(i!=goal && (cnt<(n-1)-(goal-i) || c[i][1]>1)){write(0);return 0;};
        cnt+=c[i][1];
    }
    for(int i=n;i>=n-c[goal][1]+1;i--)res=mul(res,i);
    write(res);
    return 0;
}