problem

题目描述

有两个可重集合 $n$，初始时 $m$ 只包含一个 $0$，是给定的。
执行以下操作：

在 $B$ 中随机选一个数 $y$，把 $y$ 从 $B$ 移动到 $A$。

给答案加上 $A$ 的平均值。

若 $B$ 非空，回到步骤 $1$。
求最后答案的期望。

输入格式

第一行两个整数 $n,m$，表示集合 $B$ 可以分成 $m$ 个大小为 $n$ 的部分。

solution

考虑第一个被选择的数 $x$ 的贡献，即 $\frac{1}{n\ast m}\cdot (\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n\ast m+1})\cdot x$ 【从加入后每一轮都会产生一个贡献】

发现系数具有连续性，第 $i$ 次加入的数的贡献为 $\frac{1}{n\ast m}\cdot (\frac{1}{i+1}+\frac{1}{i+2}+...+\frac{1}{n\ast m+1})\cdot x$

考虑枚举这个数是第几次被加入的，统计答案即可。

相同权值的数的所有情况贡献是完全相同的。

线性递推逆元，并处理逆元的后缀和即可。

code

#include <cstdio> #define maxn 20000005 #define mod 998244353 int n, m; int inv[maxn];int main() {freopen( "mos.in", "r", stdin );freopen( "mos.out", "w", stdout );scanf( "%d %d", &n, &m );inv[1] = 1;for( int i = 2;i <= n * m + 1;i ++ ) inv[i] = ( - mod / i * 1ll * inv[mod % i] % mod + mod ) % mod;int p = 0, f = 0;for( int i = n * m + 1;i > 1;i -- ) {f = ( 1ll * f + inv[i] ) % mod;p = ( 1ll * p + f ) % mod;} int ans = 0;for( int i = 1, x;i <= n;i ++ ) {scanf( "%d", &x );ans = ( 1ll * ans + 1ll * p * x % mod * m ) % mod;}printf( "%d\n", 1ll * ans * inv[n * m] % mod ); }

总结

以上是生活随笔为你收集整理的集合均值（逆元+数学）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。