温州网站制作推广,福州网站建设fjfzwl,信息流推广渠道,成都 企业网站建设公司价格抽象#x1f605;
我忍不了了#xff0c;直接上概率生成函数#x1f605;
首先要做过这道题 [CTSC2006] 歌唱王国
设 F i ( x ) ∑ f j x j F_i(x)\sum f_jx^j Fi(x)∑fjxj#xff0c;其中 f j f_j fj表示 ∣ T ∣ j |T|j ∣T∣j时第 i i i个人获胜的概率
设 …抽象
我忍不了了直接上概率生成函数
首先要做过这道题 [CTSC2006] 歌唱王国
设 F i ( x ) ∑ f j x j F_i(x)\sum f_jx^j Fi(x)∑fjxj其中 f j f_j fj表示 ∣ T ∣ j |T|j ∣T∣j时第 i i i个人获胜的概率
设 G ( x ) ∑ g j x j G(x)\sum g_jx^j G(x)∑gjxj其中 g j g_j gj表示 ∣ T ∣ i |T|i ∣T∣i时无人获胜概率
对于 i i i有方程 F i ( x ) G ( x ) × x m × 1 2 m − ∑ F j ( x ) × tran ( j , i ) F_i(x)G(x)\times x^m\times \frac{1}{2^m}-\sum F_j(x)\times \text{tran}(j,i) Fi(x)G(x)×xm×2m1−∑Fj(x)×tran(j,i)
注意到还有一条方程 G ( x ) x G ( x ) − ∑ F i ( x ) 1 G(x)xG(x)-\sum F_i(x)1 G(x)xG(x)−∑Fi(x)1
考虑这个算法的本质 注意到 G ( 1 ) G(1) G(1)其实就是停下来时 ∣ T ∣ |T| ∣T∣的期望
这样有 n 1 n1 n1个未知数 n 1 n1 n1个方程直接高斯消元即可。
复杂度 O ( n 3 ) O(n^3) O(n3)。
#includebits/stdc.h
#define pb push_abck
#define fi first
#define se second
#define db double
#define ll long long
#define ull unsigned long long
using namespace std;
const int P13331;
int n,m;
string str[305];
db a[505][505];
db fac2[505];
ull fac[305],h[305][305];
ull get(int i,int l,int r){return (h[i][r]-h[i][l-1])*fac[m-l];
}
void solve(){for(int i1;in1;i){for(int j1;jn1;j){if(i!j){db tmpa[j][i]/a[i][i];for(int ki;kn2;k)a[j][k]-a[i][k]*tmp;}}}
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnm;for(int i1;in;i)cinstr[i];fac[0]1;for(int i1;im;i)fac[i]fac[i-1]*P;fac2[0]1;for(int i1;im;i)fac2[i]fac2[i-1]/2;for(int i1;in;i){for(int j1;jm;j)h[i][j]h[i][j-1]str[i][j-1]*fac[j];}for(int i1;in;i){for(int j1;jn;j){for(int k1;km;k){if(get(i,k1,m)get(j,1,m-k)){a[j][i]fac2[k];}}}}for(int i1;in;i)a[i][i]1,a[i][n1]-fac2[m];for(int i1;in;i)a[n1][i]1;a[n1][n2]1;solve();for(int i1;in1;i)coutfixedsetprecision(10)a[i][n2]/a[i][i]\n;
}
