完整比赛在这儿。
杜老师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_ileq 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 imes 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
",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
",ans%mod);
return 0;
}