花生壳做网站速度,如何做与别人的网站一样的,网站建设需要哪些工具,wordpress jqproblem
题目描述
有两个可重集合 nnn#xff0c;初始时 mmm 只包含一个 000#xff0c;是给定的。 执行以下操作#xff1a;
在 BBB 中随机选一个数 yyy#xff0c;把 yyy 从 BBB 移动到 AAA。给答案加上 AAA 的平均值。若 BBB 非空#xff0c;回到步骤 111。 求最后答…problem
题目描述
有两个可重集合 nnn初始时 mmm 只包含一个 000是给定的。 执行以下操作
在 BBB 中随机选一个数 yyy把 yyy 从 BBB 移动到 AAA。给答案加上 AAA 的平均值。若 BBB 非空回到步骤 111。 求最后答案的期望。
输入格式
第一行两个整数 n,mn,mn,m表示集合 BBB 可以分成 mmm 个大小为 nnn 的部分。
solution
考虑第一个被选择的数 xxx 的贡献即 1n∗m⋅(1213...1n∗m1)⋅x\frac{1}{n*m}·(\frac{1}{2}\frac{1}{3}...\frac{1}{n*m1})·xn∗m1⋅(2131...n∗m11)⋅x 【从加入后每一轮都会产生一个贡献】
发现系数具有连续性第 iii 次加入的数的贡献为 1n∗m⋅(1i11i2...1n∗m1)⋅x\frac{1}{n*m}·(\frac{1}{i1}\frac{1}{i2}...\frac{1}{n*m1})·xn∗m1⋅(i11i21...n∗m11)⋅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 );
}
