题目

点这里看题目。

给定一个长度为 \(k\) 的非负整数序列 \(a\)。

你可以对于 \(a\) 做如下操作任意次：

• 选定 \(1\le j\le k\)，满足除了 \(a_j\) 外 \(a\) 中其它数都为正。

  而后，令 \(a_j\) 加上 \(k-1\)，令除了 \(a_j\) 外 \(a\) 中其它数减去 \(-1\)。

  （这样一次操作被称为“操作 \(j\)”）

你需要求出经过任意次操作后，可能的 \(a\) 序列有多少种。答案对 \(998244353\) 取模。

所有数据满足 \(1\le k\le 10^5,0\le a_i\le 10^6\)。

分析

一上来竟然想到 DAG 游走上面去了

注意到，最终得到的序列（不妨记为 \(a'\)）和操作顺序无关，只和每个位置操作了多少次有关。具体来说，设 \(x_i\) 表示“操作 \(i\)”总共执行的次数，那么有 \(a'_i=a_i+kx_i-\sum_t x_t\)。在此，我们记 \(m=\sum_t x_t\)，则 \(a'_i=a_i+kx_i-m\)。

考虑 \(x\) 序列即可帮助我们避免算重的问题。注意到，对于 \(k\) 个数全部操作一遍等于没有操作，所以值得考虑的 \(x\) 必须满足 \(\min x=0\)。冷静一下，发现仅统计 \(\min x=0\) 的序列也就不会算重了。具体证明如下：

Proof.

考虑两个表示操作次数序列 \(x\) 和 \(y\)，满足 \(\min x=\min y=0\) 且 \(x\neq y\)。我们同时记 \(m_x=\sum_t x_t,m_y=\sum_t y_t\)。

如果 \(m_x=m_y\)，因为 \(x\neq y\)，所以容易推出它们产生的结果序列不同。

如果 \(m_x\neq m_y\)，不妨设 \(m_x<m_y\)。反证，假设对于任意的下标 \(j\)，都有 \(a_j+kx_j-m_x=a_j+ky_j-m_y\)，于是 \(x_j<y_j\)，于是 \(y_j>x_j\ge 0\)，所以 \(\min y>0\)，矛盾。

现在我们已经解决了一半的问题，考虑另一半——即“是否存在一个可行的操作序列”的问题。

先做一些数值上的观察。注意到 \(a_i+kx_i-m\ge 0\Leftrightarrow x_i\ge \lceil\frac{\max\{m-a_i,0\}}{k}\rceil\)。进一步地，应该有 \(m=\sum_i x_i\ge \sum_i\lceil\frac{\max\{m-a_i,0\}}{k}\rceil\)。

这个条件看起来还是不太强，因为它甚至弱于“\(a\) 中不能有两个及以上的 \(0\)”。但是，我们注意到进行任意多次操作后，这个条件都必须成立。也即，对于任意的 \(0\le t\le m\)，\(t\ge \sum_i\lceil\frac{\max\{t-a_i,0\}}{k}\rceil\) 都应成立。

这个条件够强吗？至少它不弱于“至多一个 \(0\)”。我们考虑建立归纳证明：

Conclusion.

对于操作次数序列 \(x\)，记 \(m=\sum_i x_i\)，则存在一种合法且“操作 \(i\)”出现次数为 \(x_i\) 的操作序列当且仅当 \(\forall 0\le t\le m,t\ge \sum_i\lceil\frac{\max\{t-a_i,0\}}{k}\rceil\)。

Proof.

对于 \(m\) 进行归纳。首先，\(m=0\) 意味着 \(x\) 全为 \(0\)，显然是成立的。

当 \(m>0\) 时，我们需要证明充分性和必要性：

必要性

我们只需要证明，存在一个 \(i_0\) 满足 \(x_{i_0}>0\) 且“操作 \(i_0\)”合法且操作后右侧条件仍然满足，即可生成一个操作序列。假设 \(i_0\) 存在，我们设操作后的序列为 \(b\)。

记 \(w_t=\sum_{i}\lceil\frac{\max\{t-a_i,0\}}{k}\rceil\)。任取 \(0\le t<m\)，有：

\[\begin{aligned} \sum_i\left\lceil\frac{\max\{t-b_i,0\}}{k}\right\rceil&=\sum_{i\neq i_0}\left\lceil\frac{\max\{t+1-a_i,0\}}{k}\right\rceil+\left\lceil\frac{\max\{t-a_{i_0}-k+1,0\}}{k}\right\rceil\\ &=w_{t+1}-\left\lceil\frac{\max\{t+1-a_{i_0},0\}}{k}\right\rceil+\left\lceil\frac{\max\{t-a_{i_0}-k+1,0\}}{k}\right\rceil \end{aligned} \]

如果 \(t+1-a_{i_0}>0\)，那么就有 \(LHS=w_{t+1}-1\le t\)；如果 \(t+1-a_{i_0}\le 0\)，则 \(LHS=w_{t+1}\)。

贪心地想，我们令 \(i_0\) 为使得 \(x_i>0\) 且 \(a_i\) 最小的 \(i\)。注意到，如果 \(x_i=0\)，则 根据 \(x_i\ge \lceil\frac{\max\{m-a_i,0\}}{k}\rceil\) 可知 \(a_i\ge m\)。于是，对于 \(t\in [0,a_{i_0})\) 而言，\(w_{t+1}\) 的和式中无论是 \(x_i>0\) 的项还是 \(x_i=0\) 的项贡献都必然为 \(0\)，于是 \(w_{t+1}=0\)。

那么，执行“操作 \(i_0\)”合法吗？不合法的情况是，除了 \(a_{i_0}\) 以外还有数为 \(0\)。考虑 \(w_1\ge 1\) 即可知此情况不存在。

故必要性得证。

充分性

此处，我们沿用“必要性”证明的 \(b\) 和 \(i_0\)。

在此，我们不加证明地指出：

如果存在一种符合条件的操作序列，则必然存在一种操作序列，使得其第一次操作为“操作 \(i_0\)”。

类似于“必要性”证明的讨论，可以证明 \(t\in [0,m)\) 时 \(w_{t+1}\le t+1\)。再讨论一下 \(t=0\) 的情况，可知 \(w_{0}=0\)。

故充分性得证。

证明完这个重要结论之后，我们只需要枚举 \(s\) 并计算方案数即可。\(s\) 确定时，方案数可以直接插板得出。而当 \(s>\max a\) 时，对于任意 \(x_i\) 都有 \(x_i>0\)，故 \(s\) 只需枚举到 \(\max a\)。

复杂度因此为 \(O(\max a+k\log k)\)。

代码

#include <bits/stdc++.h>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int mod = 998244353;
const int MAXN = 2e6 + 5;

template<typename _T>
inline void Read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) Write( x / 10 );
    putchar( x % 10 + '0' );
}

int fac[MAXN], ifac[MAXN];

int su[MAXN];
int A[MAXN];

int K, V;

inline int Qkpow( int, int );
inline int Inv( const int &a ) { return Qkpow( a, mod - 2 ); }
inline int Mul( int x, const int &v ) { return 1ll * x * v % mod; }
inline int Sub( int x, const int &v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, const int &v ) { return ( x += v ) >= mod ? x - mod : x; }

inline int& MulEq( int &x, const int &v ) { return x = 1ll * x * v % mod; }
inline int& SubEq( int &x, const int &v ) { return ( x -= v ) < 0 ? ( x += mod ) : x; }
inline int& AddEq( int &x, const int &v ) { return ( x += v ) >= mod ? ( x -= mod ) : x; }

inline int C( int n, int m ) { return n < m ? 0 : Mul( fac[n], Mul( ifac[m], ifac[n - m] ) ); }

inline int Qkpow( int base, int indx ) {
    int ret = 1;
    while( indx ) {
        if( indx & 1 ) MulEq( ret, base );
        MulEq( base, base ), indx >>= 1;
    }
    return ret;
}

inline void Down( int &x ) { x &= x - 1; }
inline void Up( int &x ) { x += x & ( - x ); }
inline void Update( int x, int v ) { for( ; x <= K ; Up( x ) ) su[x] += v; }
inline  int Query( int x ) { int ret = 0; for( ; x ; Down( x ) ) ret += su[x]; return ret; }

inline void Init( const int &n ) {
    fac[0] = 1; rep( i, 1, n ) fac[i] = Mul( fac[i - 1], i );
    ifac[n] = Inv( fac[n] ); per( i, n - 1, 0 ) ifac[i] = Mul( ifac[i + 1], i + 1 );
}

int main() {
    Read( K );
    rep( i, 1, K )
        Read( A[i] ), V = std :: max( V, A[i] );
    std :: sort( A + 1, A + 1 + K );

    Init( V + K );
    int ans = 0, sub = 0;
    for( int s = 0, i = 1, j = 1 ; s <= V ; s ++ ) {
        for( ; i <= K && A[i] <= s ; i ++ )
            sub += A[i] / K, Update( A[i] % K + 1, +1 );
        for( ; j <= K && A[j] <  s ; j ++ );
        int low = s / K * ( i - 1 ) - sub + Query( s % K );
        if( low > s ) break;
        AddEq( ans, Sub( C( s - low + K - 1, K - 1 ), C( s - low + j - 2, K - 1 ) ) );
    }
    Write( ans ), putchar( '\n' );
    return 0;
}