8.9 正睿暑期集训营 Day6 C 风花雪月(DP)

题目链接

完整比赛在这儿

杜老师tql 8.9 正睿暑期集训营 Day6 C 风花雪月(DP)

求期望要抽卡的次数,也就是求期望经历了多少不满足状态。而每个不满足的状态对答案的贡献为\(1\),所以可以直接算概率。即\(Ans=\sum_{不满足状态s} P(s)\)。

设有\(x_i\)个\(i\),其贡献为\(s_i\)。

当\(x_i>c_i\)时,\(s_i=c_i+\frac{x_i-c_i}{4}\);

当\(x_i\leq c_i\)时,\(s_i=x_i-c_i\)。

若\(\sum s_i<0\),则是不满足状态,此时\(P=p_1^{x_1}p_2^{x_2}...p_n^{x_n}\frac{(x_1+x_2+...+x_n)!}{x_1!x_2!...x_n!}\)。

令\(f[i][j][k]\)表示当前考虑到第\(i\)种元素,贡献和为\(j\),总共选了\(k\)个的概率。

转移直接枚举\(x_i\),乘上个系数\(\frac{p_i^{x_i}}{x_i!}\)。最后\(Ans=ans\times k!\)。

\(i\)是\(10\),\(j\)最大是\(400*2\),\(k\)是\(1600\),转移\(O(1600)\),还是能过的。。吧。。

有点卡不过去。。加上强大的取模优化可以卡到\(90\)。

我们只关心不满足的状态,所以中间满足条件了的状态可以不要。令\(f[i][j][k]\)的\(j\)表示还需\(j\)的贡献才能满足条件。那么初始化\(f[0][\sum c_i][0]=1\),转移时小于等于\(0\)的\(j'\)可以忽略,且\(j\)的上限只需要\(400\)。

这样就可以轻松过了。


//7460ms	50648kb
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define mod 1000000007
#define Inv(x) FP(x,mod-2)
#define Add(x,v) (x+=v)>=LIM&&(x%=mod)
typedef long long LL;
const int N=12,M=1603;
const LL LIM=6e18; int q[N],p[N],c[N],fac[M],ifac[M],coef[M]/*coefficient*/;
LL f[N][M][405]; inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline int FP(int x,int k)
{
int t=1;
for(; k; k>>=1,x=1ll*x*x%mod)
if(k&1) t=1ll*t*x%mod;
return t;
} int main()
{
int n=read(),s=0;
for(int i=1; i<=n; ++i) s+=q[i]=read();
int inv=Inv(s); s=0;
for(int i=1; i<=n; ++i) p[i]=1ll*q[i]*inv%mod, s+=c[i]=read(); const int lim=s<<2;
fac[0]=fac[1]=1;
for(int i=2; i<=lim; ++i) fac[i]=1ll*fac[i-1]*i%mod;
ifac[lim]=Inv(fac[lim]);
for(int i=lim; i; --i) ifac[i-1]=1ll*ifac[i]*i%mod; const int sum=s;
f[0][0][sum]=1;
for(int i=0; i<n; ++i)
{
LL pw=p[i+1]; coef[0]=1;
for(int j=1,pi=pw; j<=lim; ++j) coef[j]=pw*ifac[j]%mod, pw=pw*pi%mod; int cost=c[i+1]; LL v;
for(int j=0; j<=lim-3; ++j)//f[i][j][k]:选j个 所需贡献为k
for(int k=0; k<=sum; ++k)
if((v=f[i][j][k]%mod))
for(int l=0; l+j<=lim; ++l)
{
int tmp=(l<=cost?l-cost:l-cost>>2)+cost;
if(tmp>=k) break;
Add(f[i+1][l+j][k-tmp],v*coef[l]);
}
}
LL ans=1;//0
for(int i=1; i<=lim; ++i)
{
LL tmp=0;
for(int j=1; j<=sum; ++j) tmp+=f[n][i][j]%mod;
ans+=tmp%mod*fac[i]%mod;
}
printf("%lld\n",ans%mod); return 0;
}

90分代码:

#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define D 402
#define mod 1000000007
#define Inv(x) FP(x,mod-2)
#define Add(x,v) (x+=v)>=LIM&&(x%=mod)
typedef long long LL;
const int N=12,M=1603;
const LL LIM=6e18; int q[N],p[N],c[N],fac[M],ifac[M],coef[M]/*coefficient*/;
LL f[N][M][805]; inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline int FP(int x,int k)
{
int t=1;
for(; k; k>>=1,x=1ll*x*x%mod)
if(k&1) t=1ll*t*x%mod;
return t;
} int main()
{
int n=read(),s=0;
for(int i=1; i<=n; ++i) s+=q[i]=read();
int inv=Inv(s); s=0;
for(int i=1; i<=n; ++i) p[i]=1ll*q[i]*inv%mod, s+=c[i]=read(); const int lim=s<<2;
fac[0]=fac[1]=1;
for(int i=2; i<=lim; ++i) fac[i]=1ll*fac[i-1]*i%mod;
ifac[lim]=Inv(fac[lim]);
for(int i=lim; i; --i) ifac[i-1]=1ll*ifac[i]*i%mod; f[0][0][D]=1;
const int sum=s,R=D+sum;
for(int i=0,s=0; i<n; s+=c[++i])
{
LL pw=p[i+1]; coef[0]=1;
for(int j=1,pi=pw; j<=lim; ++j) coef[j]=pw*ifac[j]%mod, pw=pw*pi%mod; int cost=c[i+1]; LL v;
for(int j=0,L=D-s; j<=lim-3; ++j)//f[i][j][k]:选j个 贡献为k
for(int k=L; k<=R; ++k)
if((v=f[i][j][k]%mod))
for(int l=0; l+j<=lim; ++l)
{
int tmp=k+(l<=cost?l-cost:l-cost>>2);
if(tmp>D+sum) break;
Add(f[i+1][l+j][tmp],v*coef[l]);
}
}
LL ans=0;
for(int i=0; i<lim; ++i)
{
LL sum=0;
for(int j=0; j<D; ++j) sum+=f[n][i][j]%mod;
ans+=sum%mod*fac[i]%mod;
}
printf("%lld\n",ans%mod); return 0;
}
上一篇:海明码 CRC冗余校验码


下一篇:jQuery html表格排序插件:tablesorter