Codeforces 1194F. Crossword Expert
考虑每一个位置的期望贡献 $P[i]$
对于第 $k$ 个位置,设 $sum=\sum_{i=1}^{k}t[k]$,那么 $T-sum$ 即为用最短时间完成完位置 $k$ 后多出来的空闲时间
如果 $T-sum>=k$ 那么这个位置一定能完成,贡献为 $1$
如果 $T<sum$ ,那么这个位置一定没法完成,贡献为 $0$
否则设 $mx=max(T-sum,k)$,那么这个位置完成的总情况数就是在多出来的时间内任选几个位置多花费 $1$
那么这个位置有 $\sum_{i=0}^{mx} \binom {mx}{i} $ 种不同的合法方案,再除以总方案数 $2^k$ 即为概率
因为价值为 $1$,那么期望贡献 $P[i]$ 就是 $\frac {1} {2^k} \sum_{i=0}^{mx} \binom {mx}{i} $
然后发现直接计算一堆组合数的复杂度是 $n^2$ 的,考虑如何优化计算过程
注意到我们每次算组合数时的 $\binom {mx} {i} $ 的 $mx$ 是单调递减的(显然只要考虑 $T-sum<k$ 时的情况),并且每次 $i$ 加一
考虑杨辉三角递推组合数时,$2\sum_{j=0}^{x}\binom {i}{j}=(\sum_{j=0}^{x}\binom {i+1}{j})+\binom {i}{x}$(这个自己画一下杨辉三角就知道了)
那么我们就可以动态维护 $now=\sum_{i=0}^{mx} \binom {mx}{i}$,然后每到下一层就 $now=now*2-\binom {i-1}{mx_{i-1}}$
然后再利用 $mx$ 的单调性直接暴力维护一下 $now$ 即可做到 $O(n)$
然后就过了,注意 $long\ long$
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline ll read()
{
ll x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=4e5+,mo=1e9+;
inline int fk(int x) { return x>=mo ? x-mo : x; }
int n,t[N],fac[N],finv[N],ans;
ll T;
inline int ksm(int x,int y)
{
int res=;
while(y) { if(y&) res=1ll*res*x%mo; x=1ll*x*x%mo; y>>=; }
return res;
}
inline int C(int x,int y) { return 1ll*fac[x]*finv[y]%mo*finv[x-y]%mo; }
int main()
{
n=read(); T=read();
fac[]=; finv[]=;
for(int i=;i<=n;i++)
{
t[i]=read();
fac[i]=1ll*fac[i-]*i%mo;
finv[i]=ksm(fac[i],mo-);
}
int i2=,now=,pre=; ll sum=;
for(int i=;i<=n;i++)
{
sum+=t[i]; i2=fk(i2+i2);
if(T-sum>=i) { ans++; continue; }
if(T-sum<) break;
int mx=T-sum;
if(!now)
{
for(int j=;j<=mx;j++) now=fk(now+C(i,j));
pre=mx; ans=fk(ans+1ll*now*ksm(i2,mo-)%mo);
continue;
}
now=fk( fk(now+now)-C(i-,pre)+mo );
while(pre>mx) now=fk(now-C(i,pre)+mo),pre--;
ans=fk(ans+1ll*now*ksm(i2,mo-)%mo);
}
printf("%d\n",ans);
return ;
}
最新文章
- MySQL实现嵌套集合模型
- ExtJs combobox模糊匹配
- (转)SQL Server 性能调优(cpu)
- PHP解析JSON和XML方法
- [转]40多个关于人脸检测/识别的API、库和软件
- 数学语言和程序语言的对比:面向过程与面向集合&;命题
- HDOJ 2021 发工资咯:)(利用了一种取余的思想)
- Effective Java Item3:Enforce the singleton property with a private constructor or an enum type
- C# 微信公众平台开发(4)-- 模版消息
- 使用flex和bison实现的sql引擎解析
- Java 集合 持有引用 &; WeakHashMap
- ubuntu 笔记一
- Golang使用pprof和qcachegrind进行性能监控
- python 动态加载类对象
- Java 浮点型与双精度数值比较
- 十二个 ASP.NET Core 例子——IOC
- Query 插件为什么要return this.each()
- 日志收集(ElasticSearch)串联查询 MDC
- Linux 网卡驱动学习(五)(收发包具体过程)【转】
- 15.翻译系列:EF 6中的级联删除【EF 6 Code-First 系列】