乒乓球

題目描述

小 $Bo$ 是某省乒乓球名列前茅的選手，現(xiàn)在他有 $n$ 顆乒乓球一字排開，第$i$顆乒乓球的權(quán)值為 $w_i$
每次他會隨機(jī)從現(xiàn)有的乒乓球中等概率選一顆拿走，然后得到的收益是這顆球左邊第一個(gè)乒乓球和右邊第一個(gè)乒乓球的權(quán)值的乘積，如果左邊沒有乒乓球或者右邊沒有乒乓球，則收益為 $0$，這個(gè)過程會重復(fù)進(jìn)行到所有球都被拿走為止
現(xiàn)在小 $Bo$ 想知道他的期望總收益
為了方便，你只需要輸出答案對 $998244353$ 取模的值.

解決方案

思路就是枚舉一對乒乓球$(i,j)$然后計(jì)算它對于答案的貢獻(xiàn).
$(i,j)$要想產(chǎn)生貢獻(xiàn),那么至少要滿足$2\le j?i\le n?1$.

考慮$i,j$兩顆乒乓球一定要在$[i+1,j?1]$之間的乒乓球全都取完才能取,這樣的情況共有$(j?i?1)!?2!?C_n^{j?i+1}?(n?(j?i+1))!$

也就是$\frac{2?n!}{(j?i)(j?i+1)}$,而最后的答案要除以$n!$,所以在這里直接除掉就可以了,也就是$\frac{2}{(j?i)(j?i+1)}$

共線即為$w_i?w_j?\frac{2}{(j?i)(j?i+1)}$

而這個(gè)值只與$(j?i)$的大小有關(guān),而如果我們將式子中第二個(gè)$w_j$反轉(zhuǎn),即改寫成$b_{n?j}$.(其中$b_i=w_{n?i}$)

那么$w_i?b_{n?j}?\frac{2}{(j?i)(j?i+1)}$

這下我們枚舉$\frac{2}{(t)(t+1)}$,找所有滿足的$(i,n?j)$對,使得$n?j?i=n?t$

顯然這就是一個(gè)求卷積的裸題了,$w$序列與$b$序列卷積的第$n?t$項(xiàng)就是我們要求的答案.

代碼

#include <iostream> #include <cstring> #include <cstdio>using 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(le+1,P-2,P) % P;ans = (ans + (a[n-le]*part % P)) % P;}std::cout << ans << std::endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的数学推导题,NTT,快速数论变换,Wannafly-乒乓球的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。