题目
点这里看题目。
分析
介绍两种做法，一种是简单的题解方法，另一种是复杂的做法。
题解
假设有 (C) 种不同的颜色，我们可以先将颜色离散化，标号为 (1,2,dots,C)。设第 (i) 种颜色数量为 (a_i)。
“不同的颜色的数量”也就是出现了的颜色的种数。因此我们可以设离散随机变量 (X_i) 表示第 (i) 种颜色是否出现，如果 (X_i=1) 则第 (i) 种颜色出现，否则 (X_i=0)，表示第 (i) 种颜色不出现。
我们需要求的是 (E[sum_{i=1}^CX_i]=sum_{i=1}^CE[X_i])，而由于 (X_i) 的取值只有 ({0,1})，所以 (E[X_i]=P(X_i=1))。我们也就是要求第 (i) 种颜色出现的概率，当我们枚举选择的糖果数量 (k) 时，使用容斥原理得到概率为：
当 (n,k) 确定时，这个式子只和 (a_i) 相关。由于 (sum_{i=1}^Ca_i=n)，所以不同的 (a_i) 只有 $ O(sqrt n)$ 种。对于不同的 (a_i) 单独计算，乘上系数即可。复杂度为 (O(nsqrt n))。
复杂做法
显然将颜色排序不会影响结果，我们将输入的 (c) 序列排序，那么对于选出来的 (k) 个糖果，只有可能在相邻的两项之间产生贡献。根据期望的线性性，我们可以枚举相邻的两项，计算它们可能带来的贡献。
枚举 (k,k>1)，可以计算所有的贡献为：
期望就还需要除掉 (inom{n}{k}) 的情况总数，下面仅对这个式子化简。
([c_i ot=c_j]) 不好搞，把它拆成 (1-[c_i=c_j])。我们先处理前面一半：
接着考虑 ([c_i=c_j])。假设 (c_i) 出现次数为 (q)，这就相当于要求 (1le j-ile q)，所以：
现在开始，式子看起来不太友好，我们改用生成函数。尝试构造 (sum_{ige 1}inom{q}{i}(i-1)x^i)，从系数入手：
对于系数的构造恰好使得我们得到的生成函数没有常数项。所以和式正好是卷积的形式，我们需要的答案为：
同样的道理，不同的 (q) 只有 (O(sqrt{n})) 种，所以对于不同的 (q) 计算一遍即可。复杂度为 (O(nsqrt{n}))。
小结：
- 比较一下两种做法，第一种做法简单的原因在于它将每种颜色单独考虑，而不像第二种是考虑一对糖果，所以才能大大简化运算；当然，第二种方法其实也用了这种思想。
- 推导生成函数的时候，以系数为突破口，常用的方法之一就是根据已有结果构造出需要的系数。
- 再次提醒用到的 (sqrt n) 性质。
代码
这里只给出第二种做法的代码：
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#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 = 1e5 + 5;
template<typename _T>
void read( _T &x )/*{{{*/
{
x = 0; char s = getchar(); int f = 1;
while( ! ( '0' <= s && s <= '9' ) ) { 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' );
}/*}}}*/
typedef std :: pair<int, int> Occurence;
std :: vector<Occurence> occ;
int fac[MAXN], ifac[MAXN];
int c[MAXN], app[MAXN];
int N;
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; }
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 ) ret = Mul( ret, base );
base = Mul( base, base ), indx >>= 1;
}
return ret;
}/*}}}*/
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( N ), Init( N );
rep( i, 1, N ) read( c[i] );
std :: sort( c + 1, c + 1 + N );
for( int i = 1, j ; i <= N ; i = j )
{
for( j = i ; j <= N && c[j] == c[i] ; j ++ );
app[j - i] ++;
}
rep( i, 1, N ) if( app[i] )
occ.push_back( std :: make_pair( i, app[i] ) );
puts( "1" );
rep( k, 2, N )
{
int ans = Mul( k - 1, C( N, k ) );
for( int i = 0 ; i < ( int ) occ.size() ; i ++ )
{
int q = occ[i].first;
int res = 0;
res = Add( res, Mul( C( N - 1, k - 1 ), q ) );
res = Sub( res, C( N, k ) );
res = Add( res, C( N - q, k ) );
ans = Sub( ans, Mul( res, occ[i].second ) );
}
write( Add( 1, Mul( ans, Inv( C( N, k ) ) ) ) ), putchar( '
' );
}
return 0;
}