CF908D New Year and Arbitrary Arrangement [概率DP]

本文主要是介绍CF908D New Year and Arbitrary Arrangement [概率DP]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

f[i][j] 表示有 i 个 a, j 个 ab 的期望, 设 A 为选 a 的概率, B 为选 b 的

如果 i + j >= k 那么再放一个 b 就可以结束, 这种情况的期望就是

转移的话

初始状态如果是 0, 0 的话

显然会死循, 因为一开始可能为 bbbbbbb...

但由于 A = 1 - B, 所以上面那个式子等价于 

所以初始状态设为 f[1][0] 即可

---

#include<bits/stdc++.h>
#define N 1050
using namespace std;
typedef long long ll;
const int Mod = 1000000007;
int k; ll pa, pb, f[N][N];
ll add(ll a, ll b){ return (a+b) % Mod;}
ll mul(ll a, ll b){ return (a*b) % Mod;}
ll power(ll a, ll b){ll ans = 1; for(;b;b>>=1){if(b&1) ans = mul(ans, a);a = mul(a, a);} return ans;
}
int main(){scanf("%d%lld%lld", &k, &pa, &pb);ll A = mul(power(pa + pb, Mod - 2), pa);ll B = mul(power(pa + pb, Mod - 2), pb);ll C = mul(A, power(Mod + 1 - A, Mod - 2));for(int i=k; i>=1; i--){for(int j=k; j>=0; j--){if(i + j >= k) f[i][j] = add(add(i, j), C);else f[i][j] = add(mul(f[i+1][j], A), mul(f[i][i+j], B));}} printf("%lld", f[1][0]); return 0;
}

 

这篇关于CF908D New Year and Arbitrary Arrangement [概率DP]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---