牛客2020寒假训练营2-C
七月 15, 2020
题意
有n道题
给出每到题做对的概率pi (取模1e9+7的意义下的pi)
问n道题答对 0 1 2 3 4…..n道的概率mod 1e9+7
如做对的概率为p=1/2 在mod 1e9+7 的意义下为p’=500000004
///没有对小数或分数的取模的概念 只有转化为除法取模
p=a/b在mod1e9+7的意义下的值为p’ p’ × b mod 1e9+7==a
某数x乘概率p 再取mod == x×a/b mod 1e9+7 除法取模等于乘逆元
上式== x×a×b的逆 mod 1e9+7 而a×b的逆==p’ 即p在mod1e9+7意义下的值
1-p 在mod 1e9+7意义下 =1-p’+mod
题解
fi,j 表示前 i道题做对 j道的概率 转移时考虑第 j 道题是否做对,
转移方程为f{i,j}=f{i−1,j}×(1−pi)+f{i−1,j−1}×pi
1 | # include<bits/stdc++.h> |
查看评论