bzoj 4481: [Jsoi2015]非诚勿扰【期望+树状数组】

2021-06-30 17:06

阅读：535

标签：计算 play i++ date getc getchar main return turn

首先很容易计算对于一个如意郎君列表里有x个男性的女性，编号排第i位的男性被选的概率是
\[ p*(1-p)^{i-1}+p*(1-p)^{i-1+n}+p*(1-p)^{i-1+n}+… \]
\[ =p*((1-p)^{i-1}+(1-p)^{i-1+n}+(1-p)^{i-1+n}+…) \]
然后我就不会了……
然后发现有个神奇的东西叫无限等比数列求和公式，只适用于公比绝对值小于1的情况：
\[ a1+a1*q+a1*q^2+……+a1*q^{inf} \]
\[ =\frac{a1-a1*q^{inf+1}}{1-q} \]
因为fabs(q)\[ =\frac{a1}{1-q} \]
然后剩下就是用树状数组求逆序对了

#include
#include
#include
#include
using namespace std;
const int N=500005;
int n,m;
long double p,t[N],ans;
struct qwe
{
    int b;
    long double p;
    qwe(int B=0,long double P=0)
    {
        b=B,p=P;
    }
};
vectora[N];
bool cmp(const qwe &a,const qwe &b)
{
    return a.b‘9‘||p=‘0‘&&p=1;i-=(i&(-i)))
        r+=t[i];
    return r;
}
int main()
{
    n=read(),m=read();
    cin>>p;
    for(int i=1;i

bzoj 4481: [Jsoi2015]非诚勿扰【期望+树状数组】

标签：计算 play i++ date getc getchar main return turn

原文地址：https://www.cnblogs.com/lokiii/p/9640598.html

上一篇：jar包打包exe可执行程序

下一篇：数据结构与算法基础-树

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：bzoj 4481: [Jsoi2015]非诚勿扰【期望+树状数组】
文章链接：http://soscw.com/index.php/essay/99936.html

亲，登录后才可以留言！

bzoj 4481: [Jsoi2015]非诚勿扰【期望+树状数组】

评论

热门文章

推荐文章

最新文章

置顶文章