题解：CF1188E Problem from Red Panda

· · 题解

题意：每次操作所有的颜色 -1，选择一种 +k。不能出现负数。求最后的颜色序列数。

设最终颜色 i 操作了 x_i 次，令 sum=\sum x_i。

不难发现最终每个颜色的个数为 a_i+x_ik-sum。

注意到上式 x_i 同时变化式子是不变的。

因为颜色序列在操作过程中每个元素均不能为负，推个式子：

\because a_i+x_ik-sum\ge 0\\ \therefore x_i\ge \lceil \frac{\max\{sum-a_i,0\}}{k}\rceil \\ \therefore sum=\sum x_i\ge \sum \lceil \frac{\max\{sum-a_i,0\}}{k}\rceil

注意到式子与 x_i 无关，且 \forall m \in [0,sum] 也满足这个式子。

不难发现 sum>a_{\max} \to x_{\min}>0，因此我们枚举 sum \in [0,a_{\max}] 即可。

那么我们先把 a 从小到大排序，发现随着 sum 的增加，需操作位置分界线 p 单调右移，双指针维护即可。显然下界之和可以用桶维护，令其为 w，则插板法简单容斥即得方案数：

\binom{s + k - w - 1}{k - 1} - \binom{s + p - w - 1}{k - 1} 
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e6+5,mod=998244353;
typedef long long ll;
ll fac[N],inv[N];
ll k,a[N],f[N];
ll fpow(ll a,ll b){
    ll res=1ll;
    while(b>=1ll){
        if(b&1ll){
            res=(res*a)%mod;
        }
        a=(a*a)%mod;
        b>>=1;
    }
    return res%mod;
}
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    inv[n]=fpow(fac[n],mod-2);
    for(int i=n;i>=1;i--){
        inv[i-1]=inv[i]*i%mod;
    }
    return ;
}
ll C(int n,int m){
    if(n<0||m<0)return 0;
    return fac[n]*inv[n-m]%mod*inv[m]%mod;
}
ll calc(ll x,ll y){
    return C(x+y-1,x);
}
int main(){
    init(2000001);
    ll n=0;
    cin>>k;
    for(int i=1;i<=k;i++){
        scanf("%lld",&a[i]);
        n+=a[i];
    }
    sort(a+1,a+k+1);
    ll res=0,p=1,ans=0;
    for(int i=0;i<=a[k];i++){
        while(a[p]<i){
            f[a[p]%k]++;
            p++;
        }
        res+=f[(i+k-1)%k];
        if(i<res)break;
        ans=(ans+(calc(i-res,k)-calc(i-res+p-k-1,k))%mod+mod)%mod;
    }
    cout<<(ans+mod)%mod;
    return 0;
}