T137223 节能主义

设平均数为$x$，那么有差值数组$b_i=a_i-x$。

考虑用类似于均分纸牌的方法来解决本题，从左到右依次考虑每堆书，直接乘上预处理好的组合数，然后清零$b_i$。

在实际操作中，将冗余的操作忽略，肯定是由大书堆向小书堆的方向移动，并且每对相邻位置的移动方向是确定的。

所以我们可以一遍扫过去，如果当前这堆书多了，就往后移；要是不够，就从后面拿过来。每次使当前位置达到平均值，并且将富余/缺口推给下一个位置。

要是后面也不够填补当前位置的缺口呢？我们可以想到，在实际操作中，书一定会先从更后面传递过来，而到了恰好下一个位置时，下一个位置多出来的书一定会是刚好填补当前位置的缺口的。所以在这一步计算方案数时，就可以直接使用“下个位置的书总数是平均数加上当前位置的缺口量”这样的状态。不过“推缺口”操作还是一样的。

具体地说，考虑$b_i$：

若$b_i>0$，则将第$i$堆中超出的所有书移到第$i+1$堆，方案数为$\dbinom{a_i}{b_i}$。
若$b_i<0$，则将第$i+1$堆中取出$-b_i$移到第$i$堆。若第$i+1$堆当前足够多，方案数为$\dbinom{a_{i+1}}{-b_i}$；若不够多，方案数为$\dbinom{x-b_i}{-b_i}$。

核心的贪心思想如上。接下来解决组合数的问题。

当$k\le 4\times 10^3$时，可以使用杨辉三角预处理组合数，时间复杂度为$O(k^2)-O(Tn)$；当$k\le 10^6$时，预处理阶乘及其乘法逆元，时间复杂度$O(k)-O(Tn)$。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<ctime>

#define IL inline

#define RG register

using namespace std;

typedef long long LL;

const int N=1e3;

const int M=1e6;

#define RI RG int

#define RC RG char

#define RL RG LL

const LL mod=998244353;

IL void qr(RI &x){

    x=0;    RC ch=getchar();

    while(!isdigit(ch))    ch=getchar();

    for(;isdigit(ch);ch=getchar())    x=(x<<3)+(x<<1)+ch-'0';

}

IL void qw(RL &x,RC ch){

    RI k=0,s[23];

    if(x==0)    s[k=1]=0;

    else     for(;x;x/=10)    s[++k]=x%10;

    for(;k;k--)    putchar(s[k]+'0');

    putchar(ch);

}

    int T,n;

    int a[N+3],b[N+3];

    LL jc[M+3],jv[M+3];

IL LL qpow(RL a,RL b){

    LL ans=1;

    for(a%=mod;b;a=a*a%mod,b>>=1)

    if(b&1)    ans=ans*a%mod;

    return ans;

}

IL LL C(RI n,RI m){

    RL x=jc[n],y=(jv[m]*jv[n-m])%mod;

    return x*y%mod;

}

IL void init(){

    jc[0]=jv[0]=1;

    for(RI i=1;i<=M;i++)

        jc[i]=(jc[i-1]*i)%mod;

    jv[M]=qpow(jc[M],mod-2);

    for(RI i=M;i>=2;i--)

        jv[i-1]=(jv[i]*i)%mod;

}

IL void sol(){

    qr(n);

    for(RI i=1;i<=n;i++)

        qr(a[i]);

    RI sum=0;

    for(RI i=1;i<=n;i++)

        sum+=a[i];

    RI ave=sum/n;

    for(RI i=1;i<=n;i++)

        b[i]=a[i]-sum/n;

    RL ans=1;

    for(RI i=1;i<n;i++)

    if(b[i]>0){

        ans=ans*C(a[i],b[i])%mod;

        a[i+1]+=b[i];

        b[i+1]+=b[i];

        a[i]-=b[i];

        b[i]=0;

    }

    else

    if(b[i]<0){

        ans=ans*C(max(ave-b[i],a[i+1]),-b[i])%mod;

        a[i+1]+=b[i];

        b[i+1]+=b[i];

        a[i]-=b[i];

        b[i]=0;

    }

    qw(ans,'\n');

}

int main(){

    init();

    qr(T);

    while(T--)

        sol();

    return 0;

}

巴特西

T137223 节能主义

最新文章

热门文章