完整比赛在这儿。
杜老师tql 。
求期望要抽卡的次数，也就是求期望经历了多少不满足状态。而每个不满足的状态对答案的贡献为\(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;
}