CF908D Arbitrary Arrangement

题目大意：

给定三个数\(k\) , \(p_a\) , \(p_b\)
每次有\(\frac{p_a}{p_a+p_b}\)的概率往后面添加一个'a'
每次有\(\frac{p_b}{p_a+p_b}\)的概率往后面添加一个'b'
当出现了\(k\)个形如 \(ab\) 的子序列（不用连续）时停止
求最后期望得到的ab子序列个数。答案对\(10^9+7\)取模。

思路与解法：

\(f[i][j]\) 表示前缀中有 \(i\) 个'a'，有 \(j\) 个'ab'子串的串的期望最终'ab'个数。
转移太容易了：
( 1 ) \(i+1\)是'a': \(\ \ \)\(f[i][j] = f[i][j] + \frac{p_a}{p_a+p_b}*f[i+1][j]\)
( 2 ) \(i+1\)是'b':\(\ \ \) \(f[i][j] = f[i][j] + \frac{p_b}{p_a+p_b}*f[i][i+j\ ]\)
显然形如\(bbbbb...bbbabbabab\)这样的串，在第一个'a'之前的部分都是没有意义的。
所以我们的目标状态为\(f[1][0]\)，代表所有串。
但显然这样是没法转移的，因为\(a\)也可能会无限制的增长。
考虑把这种情况单独算：
若\(k \leq i+j\)，设\(S = f[i][j]\) , \(p_a = \frac{p_a}{p_a+p_b}\) , \(p_b = \frac{p_b}{p_a+p_b}\)。
推一波式子：
\[S = (i+j)p_b + p_a(i+j+1)p_b + p_a^2(i+j+2)p_b+....\]
\[p_aS = p_a(i+j)p_b + p_a^2(i+j+1)p_b + p_a^3(i+j+2)p_b+....\]
\[(1-p_a)S = (i+j)p_b + p_b(p_a+p_a^2+p_a^3+....)\]
\[(1-p_a)S = (i+j)p_b + p_b\frac{p_a(1-p_a^∞)}{1-p_a}\]
上面那个是等比数列求和公式，其中又有：\(p_a + p_b = 1\) ,\(\ \) \((1-p_a^∞)\ = 1\) , 所以
\[p_bS = (i+j)p_b + p_b\frac{p_a}{p_b}\]
\[f[i][j] = S = (i + j) + \frac{p_a}{p_b}\]
所以转移时，如果\(k \leq i+j\)，用公式算，否则\(DP\)转移，最终答案存在\(f[1][0]\)中。

实现代码：

#include<bits/stdc++.h>
#define RG register
#define ll long long
#define _ 2005
#define mod 1000000007
using namespace std;
ll f[ _ ][ _ ] , k , pa , pb , invb , inv;

inline ll Pow(RG ll T,RG ll js,RG ll S){
while(js){if(js&1)S=S*T%mod; T=T*T%mod; js>>=1;}return S;}

int main(){
    cin >> k >> pa >> pb;
    invb = Pow( pb , mod-2 , 1 );
    inv = Pow( (pa+pb)%mod , mod-2 , 1 );
    for(RG int i = k; i >= 0; i --)
        for(RG int j = k; j >= 0; j --){
            if(!i && !j)continue;
            if(i + j >= k)
                f[ i ][ j ] = ( (i + j) + pa*invb%mod )%mod;
            else {
                f[ i ][ j ] += f[ i+1 ][ j ] * pa %mod * inv % mod;
                f[ i ][ j ] += f[ i ][ i+j ] * pb %mod * inv %mod;
                f[ i ][ j ] %= mod;
            }
        }
    cout << f[1][0] ;  return 0;
}

巴特西

CF908D Arbitrary Arrangement

题目大意：

思路与解法：

实现代码：

最新文章

热门文章