题目链接
题解
我们用\(dp[i][j]\)表示前缀包含\(i\)个\(a\),\(j\)个\(ab\)子串的所有字符串,得到的期望\(ab\)子串的个数.
如何转移？
在这个前缀后面加上一个\(a\):\(dp[i][j]+=dp[i+1][j] \times \frac{P_a}{P_a+P_b}\)
概率就是\(\frac{P_a}{P_a+P_b}\)
在这个前缀后面加上一个\(b\):\(dp[i][j]+=dp[i][i+j] \times \frac{P_b}{P_a+P_b}\)
概率是\(\frac{P_b}{P_a+P_b}\)
边界？
答案是\(dp[1][0]\)
边界是什么？
边界不止可能是固定的\(j\),还需要包含一些例如前缀无穷多个\(a\)的情况,因为一旦出现一个\(b\)就会使一般的递推循环\(i\)增加到无穷大.(转移方程加一个\(b\)直接加到\(i+j\))
数学过程计算出初始状态
令\(P_a=\frac {P_a}{P_a+P_b}\),\(P_b=\frac {P_b}{P_a+P_b}\),\(S=dp[i][j]\)
列出式子：
\[S=(i+j)P_b+P_a(i+j+1)P_b+P_a^2(i+j+2)P_b+……\]
左右同乘一个\(P_a\)：
\[P_aS=P_a(i+j)P_b+P_a^2(i+j+1)P_b+……\]
错位相减：
\[S-P_aS=(i+j)P_b+(P_a+P_a^2+P_a^3+……)P_b\]
等比数列：
\[(1-P_a)=(i+j)P_b+\frac{P_a(1-P_a^\infty)P_b}{1-P_a}\]
因为\(lim_{x\to\infty}P_a^x\)无限接近与0,所以看作0.
极限是这样理解的吧QAQ,有错误求dalao指出
\(1-P_a\)不就是\(\frac{P_a+P_b}{P_a+P_b}\ -\ \frac{P_a}{P_a+P_b}\)
化简一下不就是\(\frac{P_b}{P_a+P_b}\)不就是现在的\(P_b\)
带入
\[P_bS=(i+j)P_b+\frac{P_a+P_b}{P_b}\]
最后把\(p_b\)除到右边去.
\[S=i+j+\frac{P_a}{P_b}\]
得到初始状态
\[dp[i][j]=i+j+\frac{P_a}{P_b}\]
然后我们要记得及时取模,所以\(\frac{P_a}{P_b}\)如何取模又恶心到了.
求一下\(P_b\)的逆元就好了.
也就是\(ksm(P_b,mod-2)\)
最后一发记忆化搜索避免无脑循环边界.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std ; template<class T>void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return ; } #define LL long long const int maxn=1001; const int mod=1e9+7; LL k,pa,pb,dp[maxn][maxn]; LL ksm(LL x,LL b){ LL ans=1; while(b){ if(b&1) ans=ans*x%mod; (x=x*x)%=mod; b>>=1; } return ans; } LL inv(LL x){return ksm(x,mod-2);} LL dfs(int i,int j){ if(i+j>=k) return (i+j+(pa*inv(pb))%mod)%mod; if(dp[i][j]!=-1) return dp[i][j]; return dp[i][j]=(((dfs(i+1,j)*pa)%mod+(dfs(i,j+i)*pb)%mod)*inv(pa+pb)%mod)%mod; } int main() { read(k),read(pa),read(pb); memset(dp,-1,sizeof(dp)); printf("%lld",dfs(1,0)%mod); return 0; } |
By:Wahacer
2018.1.3
15:51