湖南畅想网站建设,怎么早网站上放广告,ui设计是什么工作,重庆在线官网乒乓球
题目描述
小 BoBoBo 是某省乒乓球名列前茅的选手#xff0c;现在他有 nnn 颗乒乓球一字排开#xff0c;第iii颗乒乓球的权值为 wiw_iwi 每次他会随机从现有的乒乓球中等概率选一颗拿走#xff0c;然后得到的收益是这颗球左边第一个乒乓球和右边第一个乒乓球的权值…乒乓球
题目描述
小 BoBoBo 是某省乒乓球名列前茅的选手现在他有 nnn 颗乒乓球一字排开第iii颗乒乓球的权值为 wiw_iwi 每次他会随机从现有的乒乓球中等概率选一颗拿走然后得到的收益是这颗球左边第一个乒乓球和右边第一个乒乓球的权值的乘积如果左边没有乒乓球或者右边没有乒乓球则收益为 000这个过程会重复进行到所有球都被拿走为止 现在小 BoBoBo 想知道他的期望总收益 为了方便你只需要输出答案对 998244353998244353998244353 取模的值.
解决方案
思路就是枚举一对乒乓球(i,j)(i,j)(i,j)然后计算它对于答案的贡献. (i,j)(i,j)(i,j)要想产生贡献,那么至少要满足2≤j−i≤n−12 \le j-i \le n-12≤j−i≤n−1.
考虑i,ji,ji,j两颗乒乓球一定要在[i1,j−1][i1,j-1][i1,j−1]之间的乒乓球全都取完才能取,这样的情况共有(j−i−1)!∗2!∗Cnj−i1∗(n−(j−i1))!(j-i-1)!*2!*C_n^{j-i1}*(n-(j-i1))!(j−i−1)!∗2!∗Cnj−i1∗(n−(j−i1))!
也就是2∗n!(j−i)(j−i1)\frac{2*n!}{(j-i)(j-i1)}(j−i)(j−i1)2∗n!,而最后的答案要除以n!n!n!,所以在这里直接除掉就可以了,也就是2(j−i)(j−i1)\frac{2}{(j-i)(j-i1)}(j−i)(j−i1)2
共线即为wi∗wj∗2(j−i)(j−i1)w_i*w_j*\frac{2}{(j-i)(j-i1)}wi∗wj∗(j−i)(j−i1)2
而这个值只与(j−i)(j-i)(j−i)的大小有关,而如果我们将式子中第二个wjw_jwj反转,即改写成bn−jb_{n-j}bn−j.(其中biwn−ib_i w_{n-i}biwn−i)
那么wi∗bn−j∗2(j−i)(j−i1)w_i*b_{n-j}*\frac{2}{(j-i)(j-i1)}wi∗bn−j∗(j−i)(j−i1)2
这下我们枚举2(t)(t1)\frac{2}{(t)(t1)}(t)(t1)2,找所有满足的(i,n−j)(i,n-j)(i,n−j)对,使得n−j−in−tn-j-i n-tn−j−in−t
显然这就是一个求卷积的裸题了,www序列与bbb序列卷积的第n−tn-tn−t项就是我们要求的答案.
代码
#include iostream
#include cstring
#include cstdiousing namespace std;
typedef long long LL;
const int N 1 20;
const int P 998244353;
const int G 3;
const int NUM 20;LL wn[NUM];
LL a[N], b[N];LL quick_mod(LL a, LL b, LL m)
{LL ans 1;a % m;while(b){if(b 1){ans ans * a % m;b--;}b 1;a a * a % m;}return ans;
}void GetWn()
{for(int i 0; i NUM; i){int t 1 i;wn[i] quick_mod(G, (P - 1) / t, P);}
}
void Rader(LL a[], int len)
{int j len 1;for(int i 1; i len - 1; i){if(i j) swap(a[i], a[j]);int k len 1;while(j k){j - k;k 1;}if(j k) j k;}
}void NTT(LL a[], int len, int on)
{Rader(a, len);int id 0;for(int h 2; h len; h 1){id;for(int j 0; j len; j h){LL w 1;for(int k j; k j h / 2; k){LL u a[k] % P;LL t w * a[k h / 2] % P;a[k] (u t) % P;a[k h / 2] (u - t P) % P;w w * wn[id] % P;}}}if(on -1){for(int i 1; i len / 2; i)swap(a[i], a[len - i]);LL inv quick_mod(len, P - 2, P);for(int i 0; i len; i)a[i] a[i] * inv % P;}
}void Conv(LL a[], LL b[], int n)
{NTT(a, n, 1);NTT(b, n, 1);for(int i 0; i n; i)a[i] a[i] * b[i] % P;NTT(a, n, -1);
}
LL Fac[N];
int n;
int main()
{ Fac[0] 1;for(int i 1;i N;i) {Fac[i] Fac[i-1] * i % P;}GetWn();std::cin n;for(int i 0;i n;i){ std::cin a[i];b[n-i] a[i];}int len 1;while(len n) len 1;len 1;Conv(a,b,len);LL ans 0;for(int le 2;le n-1;le) {LL part 2 * quick_mod(le,P-2,P) % P * quick_mod(le1,P-2,P) % P;ans (ans (a[n-le]*part % P)) % P;}std::cout ans std::endl;return 0;
}
