题目

点这里看题目。

分析

这里有一个很重要的转化——如果某一列已经满了，我们仍然认为它可以 " 装 " 人，只不过没有效果而已。

对于某个操作序列，我们现在可以只看有效的操作。那么有 \(p\) 列已满的情况下，选出 \(n-p\) 中某一列概率为：

看起来很合理，不是吗？

于是回到原问题，我们可以枚举某一列求解，不妨为第 \(i\) 列。此时就相当于操作序列中，恰好有 \(a_i\) 个 \(i\) 且最后一个为 \(i\) ，此外对于所有 \(j\not =i\) 都有至少 \(a_j\) 个 \(j\) ；不难列出这种情况的生成函数：

最终，对于 \(F_i(x)=\sum_{k\ge 0}f_{i,k}\frac{x^k}{k!}\) ，我们得到答案为 \(\sum_{k\ge 0}f_{i,k}=\sum_{k\ge 0}k![x^k]F_i(x)\) 。

注意到 \(F_i(x)\) 的形式其实是多项 \(\alpha x^\beta e^{\frac{\gamma}{n}x}\) 之和，我们可以单独对每一项进行计算并求和。而对于其中一项，可以得到：

那么它对答案的贡献为：

这里是广义二项式定理，不要用成常规二项式定理了。

因此我们可以对于每一种 \(x^{\beta}e^{\frac{\gamma}{n}x}\) 计算它的 \(\alpha\) ，然后就可以愉快地计算了！

如果暴力做可能会变成 \(O(n^4(\sum a)^2)\) ，做一个简单的退背包就可以优化到 \(O(n^3(\sum a)^2)\) 。

小结：

1. 最开始的转化相当重要（也很巧妙），在 [PKUWC2018]猎人杀 中也有相似的操作。
2. 对于 \(x^{\beta}e^{\frac{\gamma}{n}x}\) 的相似单项的处理，是很常用的方法。

代码

#include <cstdio>

#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 = 35, MAXM = 905;

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

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

int dp[MAXN][MAXM], tmp[MAXN][MAXM];

int fac[MAXM], ifac[MAXM], inv[MAXM];
int A[MAXN];
int N, M;

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

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

void Init()
{
	fac[0] = 1; rep( i, 1, M ) fac[i] = Mul( fac[i - 1], i );
	ifac[M] = Inv( fac[M] ); per( i, M - 1, 0 ) ifac[i] = Mul( ifac[i + 1], i + 1 );
	inv[1] = 1; rep( i, 2, M ) inv[i] = Mul( inv[mod % i], mod - mod / i );
}

int main()
{
	read( N ), M = 0;
	rep( i, 1, N ) read( A[i] ), M += A[i];
	Init(), dp[0][0] = 1;
	rep( i, 1, N )
		per( j, N, 0 )
			per( k, M, 0 )
			{
				dp[j][k] = mod - dp[j][k];
				if ( j ) dp[j][k] = Add( dp[j][k], dp[j - 1][k] );
				for ( int s = 1, pw = inv[N] ; s < A[i] && s <= k ; s ++, pw = Mul( pw, inv[N] ) )
					dp[j][k] = Sub( dp[j][k], Mul( dp[j][k - s], Mul( ifac[s], pw ) ) );
			}
	int ans = 0;
	rep( i, 1, N )
	{
		ans = 0;
		rep( j, 0, N )
			rep( k, 0, M )
			{
				tmp[j][k] = dp[j][k];
				if ( j ) tmp[j][k] = Sub( tmp[j][k], tmp[j - 1][k] );
				for ( int s = 1, pw = inv[N] ; s < A[i] && s <= k ; s ++, pw = Mul( pw, inv[N] ) )
					tmp[j][k] = Add( tmp[j][k], Mul( tmp[j][k - s], Mul( ifac[s], pw ) ) );
				tmp[j][k] = mod - tmp[j][k];
			}
		rep( j, 0, N )
		{
			int pw = Qkpow( inv[N], A[i] );
			per( k, M, A[i] - 1 )
				tmp[j][k] = Mul( tmp[j][k - A[i] + 1], Mul( ifac[A[i] - 1], pw ) );
			rep( k, 0, A[i] - 2 ) tmp[j][k] = 0;
		}
		rep( m, 0, N - 1 )
		{
			int stp = Mul( N, inv[N - m] );
			for ( int t = 0, pw = stp ; t <= M ; t ++, pw = Mul( pw, stp ) )
				ans = Add( ans, Mul( Mul( pw, fac[t] ), tmp[m][t] ) );
		}
		write( ans ), putchar( i == N ? '\n' : ' ' );
	}
	return 0;
}