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

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

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

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<functional>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> 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 <class T>
int upmin(T &a, const T &b){return (b<a?a=b,1:0);}
template <class T>
int upmax(T &a, const T &b){return (b>a?a=b,1:0);}
namespace io
{
const int SIZE=(1<<20)+1;
char ibuf[SIZE],*iS,*iT;
char obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1;
int getc()
{
(iS==iT?iS=ibuf,iT=ibuf+fread(ibuf,1,SIZE,stdin):0);
return iS==iT?EOF:*(iS++);
}
int f;
char c;
template <class T>
void get(T &x)
{
f=1;
for(c=getc();(c<'0'||c>'9')&&c!='-';c=getc());
(c=='-'?f=-1,c=getc():0);
x=0;
for(;c>='0'&&c<='9';c=getc())
x=x*10+c-'0';
x*=f;
}
void flush()
{
fwrite(obuf,1,oS-obuf,stdout);
oS=obuf;
}
void putc(char x)
{
*(oS++)=x;
if(oS==oT)
flush();
}
int a[55],t;
template <class T>
void put(T x)
{
if(!x)
putc('0');
x<0?putc('-'),x=-x:0;
while(x)
{
a[++t]=x%10;
x/=10;
}
while(t)
putc(a[t--]+'0');
}
void space()
{
putc(' ');
}
void enter()
{
putc('\n');
}
struct flusher
{
~flusher()
{
flush();
}
}
io_flusher;
}
const int infi=0x3fffffff;
const ll infll=0x3fffffffffffffffll;
const int N=100010;
const ll p=1000000007;
ll fp(ll a,ll b)
{
ll s=1;
for(;b;b>>=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<=t;x+=x&-x)
res=res*d[x]%p;
return res;
}
void solve()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld%d",&a[i],&b[i]);
a[i]=a[i]*inv100%p;
c[i]=b[i];
}
sort(c+1,c+n+1);
t=unique(c+1,c+n+1)-c-1;
for(int i=1;i<=n;i++)
b[i]=lower_bound(c+1,c+t+1,b[i])-c;
for(int i=1;i<=n;i++)
d[i]=1;
ll ans=0;
for(int i=1;i<=n;i++)
{
ans=(ans+a[i]*sum(b[i]+1))%p;
add(b[i],1-a[i]);
}
ans=(ans%p+p)%p;
printf("%lld\n",ans);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
solve();
return 0;
}

最新文章

  1. iOS开发系列--Swift语言
  2. Python Web.py与AJAX交互
  3. C#的Raw Socket实现网络封包监视
  4. LeetCode Sum Root to Leaf Numbers(DFS)
  5. 微信公共服务平台开发(.Net 的实现)8-------处理图片(上传下载发送)
  6. Sublime text3 安装
  7. NOIP201101&amp;&amp;05
  8. linux上配置subversion服务器端安装配置并使用svn,windows本地检出,设置同步更新服务器的钩子
  9. HDU 4464 Browsing History(最大ASCII的和)
  10. C 函数 strstr 的高效实现
  11. AWS(0) - Amazon Web Services
  12. C语言根据函数名调用对应的函数
  13. 经典CSS坑:如何完美实现垂直水平居中?
  14. 8款非常不错的.Net反编译利器
  15. Python中的序列操作
  16. 从源码看Spring Security之采坑笔记(Spring Boot篇)
  17. [luogu3810][bzoj3262][陌上花开]
  18. java 权重随机算法实现
  19. Lazarus下改变DBGrid记录的颜色,与Delphi不同了。
  20. 关于开发板用tftp下载失败分析

热门文章

  1. 2.Vue子组件给父组件通信
  2. CentOS6.5/7安装配置Samba
  3. __main__ — Top-level script environment
  4. nginx代理前端项目
  5. spring boot配置项profiles active
  6. dropna()函数
  7. linux 软连接的使用
  8. Spring MVC 向页面传值-Map、Model和ModelMap https://www.cnblogs.com/caoyc/p/5635878.html
  9. gradle阿里云镜像配置
  10. 四种pop模式介绍