找深圳网站建设,汝州市建设局网站,php 中英双语网站源码,网站 编程 语言正题
题目链接:https://gmoj.net/senior/#main/show/6067 题目大意 nnn个点的一张竞赛图#xff0c;第iii个点向第jjj个点(ij)(ij)(ij)连边的概率是ppp#xff0c;否则就是第jjj个点向第iii个点连边。
对于每个i(in)i(in)i(in)求出能够选出一个大小…正题
题目链接:https://gmoj.net/senior/#main/show/6067 题目大意
nnn个点的一张竞赛图第iii个点向第jjj个点(ij)(ij)(ij)连边的概率是ppp否则就是第jjj个点向第iii个点连边。
对于每个i(in)i(in)i(in)求出能够选出一个大小为iii的集合使得这个集合的所有点都连向集合外的所有点的概率。 解题思路
设fi,jf_{i,j}fi,j表示iii个点能选出jjj个的概率那么每次考虑是加在后面就有方程fi,jfi−1,j∗(1−p)jfi−1,j−1∗pi−jf_{i,j}f_{i-1,j}*(1-p)^jf_{i-1,j-1}*p^{i-j}fi,jfi−1,j∗(1−p)jfi−1,j−1∗pi−j 如果每次考虑加在前面就有fi,jfi−1,j∗pjfi−1,j−1∗(1−p)i−jf_{i,j}f_{i-1,j}*p^jf_{i-1,j-1}*(1-p)^{i-j}fi,jfi−1,j∗pjfi−1,j−1∗(1−p)i−j
联立上面两个式子可以得到fi−1,j∗(1−p)jfi−1,j−1∗pi−jfi−1,j∗pjfi−1,j−1∗(1−p)i−jf_{i-1,j}*(1-p)^jf_{i-1,j-1}*p^{i-j}f_{i-1,j}*p^jf_{i-1,j-1}*(1-p)^{i-j}fi−1,j∗(1−p)jfi−1,j−1∗pi−jfi−1,j∗pjfi−1,j−1∗(1−p)i−j ⇒fi−1,jfi−1,j−1(1−p)i−j−pi−jpj−(1−p)J\Rightarrow f_{i-1,j}f_{i-1,j-1}\frac{(1-p)^{i-j}-p^{i-j}}{p^j-(1-p)^J}⇒fi−1,jfi−1,j−1pj−(1−p)J(1−p)i−j−pi−j
也就是fn,jfn,j−1(1−p)i−j−pi−jpj−(1−p)Jf_{n,j}f_{n,j-1}\frac{(1-p)^{i-j}-p^{i-j}}{p^j-(1-p)^J}fn,jfn,j−1pj−(1−p)J(1−p)i−j−pi−j
这样处理逆元就可以线性递推了注意对于p12p\frac{1}{2}p21的时候分母为000理解一下的话可以知道iii的答案就是将n−in-in−i分割成i1i1i1个可空段然后每一种分割贡献都是(1n−i)i(\frac{1}{n-i})^i(n−i1)i也就是答案就是Cni∗(1n−i)iC_n^i*(\frac{1}{n-i})^iCni∗(n−i1)i同理是逆元做就好了。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e610,P998244353;
ll n,p,pw[N],qw[N],f[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void print(ll x){if (x9) print(x/10); putchar(x%1048); return;
}
int C(int n,int m)
{return pw[n]*qw[m]%P*qw[n-m]%P;}
int main()
{freopen(more.in,r,stdin);freopen(more.out,w,stdout);scanf(%lld%lld,n,p);pw[0]qw[0]f[0]1;if(p(1-pP)%P){for(int i1;in;i)pw[i]pw[i-1]*i%P,qw[i]power(pw[i],P-2);for(int i1;in;i)print(C(n,i)*power(power(p,n-i),i)%P),putchar( );}else{for(int i1;in;i)pw[i]pw[i-1]*p%P,qw[i]qw[i-1]*(1-p)%P;for(int i1;in;i){f[i]f[i-1]*(pw[n-i1]-qw[n-i1])%P*power(pw[i]-qw[i],P-2)%P;print((f[i]P)%P);putchar( );}}return 0;
}
