neuoj1472 yuki的氪金之旅（倒置树状数组

2020-12-13 15:29

阅读：352

标签：fun 除法 pmi flush type air map put fwrite

这题一直re不造为啥。。后来yww大神把树状数组“倒过来”就过了，倒过来的好处是算sum(d[i]+1)就行，不涉及除法，不用求逆元。

题意：初始手牌颜值是0，一共抽卡n次，第i次抽卡有pi的概率能抽到颜值为di的卡，若di>当前手牌颜值，则替换，最后问改变手牌次数的期望。

做法：树状数组维护前缀概率积。先把di离散化，di作为下标，pi作为值，逆元用费马小定理那个推论，本质就是求每次改变手牌的概率，第i次就是pi(1-pj)(1-pk)...(其中j,k

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair pii;
typedef pair pll;
void open(const char *s){
#ifndef ONLINE_JUDGE
    char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
void open2(const char *s){
#ifdef DEBUG
    char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
template 
int upmin(T &a, const T &b){return (b
int upmax(T &a, const T &b){return (b>a?a=b,1:0);}
namespace io
{
    const int SIZE=(1
    void get(T &x)
    {
        f=1;
        for(c=getc();(c‘9‘)&&c!=‘-‘;c=getc());
        (c==‘-‘?f=-1,c=getc():0);
        x=0;
        for(;c>=‘0‘&&c
    void put(T x)
    {
        if(!x)
            putc(‘0‘);
        x>=1,a=a*a%p)
		if(b&1)
			s=s*a%p;
	return s;
}
const ll inv100=fp(100,p-2);
ll a[N],d[N];
int b[N],c[N];
int n,t;
void add(int x,ll v)
{
	for(;x;x-=x&-x)
		d[x]=d[x]*v%p;
}
ll sum(int x)
{
	ll res=1;
	for(;x

neuoj1472 yuki的氪金之旅（倒置树状数组

标签：fun 除法 pmi flush type air map put fwrite

原文地址：https://www.cnblogs.com/wzgg/p/11581986.html

上一篇：WebApi学习笔记04：使用webapi模板--实体类--状态码--视图

下一篇：WPF自定义控件（二）——TextBox

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：neuoj1472 yuki的氪金之旅（倒置树状数组
文章链接：http://soscw.com/essay/35154.html

亲，登录后才可以留言！

neuoj1472 yuki的氪金之旅（倒置树状数组

评论

热门文章

推荐文章

最新文章

置顶文章