我们可以把题目中的选择(k-1)种颜色,并且全部改成剩下那种颜色改为选择一种颜色的球增加(k)个,然后所有颜色的球减少(1)个
然后考虑一个状态(b)能否在第(x)轮到达.对于每一位(i),需要在之前操作中选择(frac{b_i-(a_i-x)}{k})次才可以到达(注意这里的次数要是整数,否则不合法).再根据题目的一些条件,可以发现经过(x)轮能到达(b)状态当且仅当
- (forall i,k|(b_i-(a_i-x)))且(sum_{i=1}^{k}frac{b_i-(a_i-x)}{k}=x)
- 过程中所有的(a_i)要为非负整数
条件2可以推出对于一个(a_i),必须在前(a_i+1)轮内对(i)加一次(k).同理,要在前(a_i+k+1)轮内对(i)加两次(k),要在前(a_i+2k+1)轮内对(i)加三次(k)...依此类推
由于每轮只能给一个颜色(i)加(k),所以随着轮数的增加,我们必须要用一些轮去给某些(i)加(k)来保持非负,如果对于(x)轮可以操作到,且在(x+1)轮时,前(x+1)的轮都不够做完前面所有颜色(i)所必要的加(k)次数了,那么也就意味着(x)轮为最多能操作的轮数,并且可以发现如果(x)是有限的,那么一定满足(x<k),因为给一个数加(k)后,至少后(k)轮都不必要再加(k),也就是在满足操作轮数尽可能多的情况下一个数在(k)轮内只会被加一次,如果出现不满足的情况,那么一定没有一个(i)加了超过(1)次(k)
然后考虑轮数有限的情况下的方案.枚举总共操作轮数(x),我们可以发现不管给某个颜色(i)加多少次(k),这个当前的(a_i')和初始(a_i)一定满足(a_i-a_i'equiv xpmod {k}),也就是轮数有限的情况下每种操作轮数后得到的状态一定两两不同.那么设(x)轮要执行(c_x)次必要的加(k)操作,剩下操作的可以任意分配给每个(i),可以发现这里操作不用考虑顺序,且操作出的状态只和给每种颜色分配的次数有关且一一对应,方案数就可以写成(inom{x-c_x+k-1}{k-1})
还有可能可以操作无限次.我们可以由前面的一些性质推导出(xmod k)不同的(x)得到的状态不会算重.反之,(xmod k)相同的状态是会算重的,不过可以发现(x)更小的状态一定会在(x)更大的状态算重,因为这个操作是无限轮的,那么你用这两个(x)之间相差的(pk)轮分别给每个颜色加(p)次从而得到一样的状态.所以对于每个(jin[0,k)),我们只要在一个尽量大的(x)(满足(k|(x-j)))处给答案加上(inom{x-c_x+k-1}{k-1})即可,大概在(1e6)及更大的数左右取(因为再往后走(x-c_x)会是一个定值,即不会有其他的新状态)
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
using namespace std;
const int N=2e6+10,mod=998244353;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return x*w;
}
void ad(int &x,int y){x+=y,x-=x>=mod?mod:0;}
int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;}return an;}
int ginv(int a){return fpow(a,mod-2);}
int n,m,mx,a[N],c[N],b[N],fac[N],iac[N];
int C(int a,int b){return b<0||a<b?0:1ll*fac[a]*iac[b]%mod*iac[a-b]%mod;}
int main()
{
fac[0]=1;
for(int i=1;i<=N-5;++i) fac[i]=1ll*fac[i-1]*i%mod;
iac[N-5]=ginv(fac[N-5]);
for(int i=N-5;i;--i) iac[i-1]=1ll*iac[i]*i%mod;
n=rd();
for(int i=1;i<=n;++i)
{
a[i]=rd();
mx=max(mx,a[i]),++c[a[i]];
}
for(int i=1,s=0;i<=n;++i)
{
s+=c[i-1];
if(s>i) break;
++m;
}
int ans=0;
if(m<n)
{
for(int i=0,s=0;i<=m;++i)
{
ad(ans,C(i-s+n-1,n-1));
s+=c[i];
}
}
else
{
int s=0;
for(int i=1;i<=n;++i)
{
s+=max((mx-1-a[i]+n)/n,0);
if(a[i]!=mx) ++b[a[i]%n];
}
for(int i=n,j=mx;i;--i,--j)
{
ad(ans,C(j-s+n-1,n-1));
s-=b[(j+n-1)%n],b[(j+n-1)%n]-=j?c[j-1]:0;
}
}
printf("%d
",ans);
return 0;
}