dp math probabilities *2200

Please click on ads to support us..

Python Code:

n, a, b = map(int, input().split())
P = 10 ** 9 + 7
def inv(x): return pow(x, P - 2, P)
A = a * inv(a + b)
B = b * inv(a + b)
C = a * inv(b)
f = [[0] * 1005 for i in range(1005)]
for i in range(n, 0, -1):
   for j in range(n - 1, -1, -1):
      if(i + j >= n): f[i][j] = (i + j + C) % P
      else: f[i][j] = (A * f[i + 1][j] + B * f[i][j + i]) % P
print(f[1][0])

C++ Code:

#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define sws ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define teto(a, b) ((a+b-1)/(b))
using namespace std;

// Extra
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//

const int MAX = 300010;
const ll MOD = (int)1e9 +7;
const int INF = 1e9;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ld EPS = 1e-8;

ll fexp(ll b, ll e) {
    if(e == 0) return 1;
    ll res = fexp(b, e/2);
    res = (res * res) % MOD;
    if(e%2) res = (res * b) % MOD;
    return res; 
}

ll inv(ll a) {
    return fexp(a, MOD-2);
}

ll k, pa, pb;
ll tab[2002][2002];
ll ipapb;

ll dp(int qa, int s) {
    if(qa >= s) {
        ll p = (pa * ipapb) % MOD;
        return (qa + p*inv(MOD + 1-p)) % MOD;
    }
    if(s <= 0) {
        return 0;
    }

    if(tab[qa][s] != -1) return tab[qa][s];

    ll pegaa = (dp(qa+1, s) * pa) % MOD;
    pegaa = (pegaa * ipapb) % MOD;

    ll pegab = ((qa + dp(qa, s-qa)) * pb) % MOD;
    pegab = (pegab * ipapb) % MOD;

    ll res = (pegaa + pegab) % MOD;

    return tab[qa][s] = res;
}

int main() {
    sws;
    memset(tab, -1, sizeof(tab));
    cin >> k >> pa >> pb;

    ipapb = inv(pa + pb);

    cout << dp(1, k) << endl;

    return 0;
}


Comments

Submit
0 Comments
More Questions

467B - Fedor and New Game
252C - Points on Line
735C - Tennis Championship
992A - Nastya and an Array
554A - Kyoya and Photobooks
79B - Colorful Field
265B - Roadside Trees (Simplified Edition)
1362C - Johnny and Another Rating Drop
1214C - Bad Sequence
1091B - New Year and the Treasure Geolocation
244A - Dividing Orange
1061C - Multiplicity
1312A - Two Regular Polygons
801A - Vicious Keyboard
510B - Fox And Two Dots
616D - Longest k-Good Segment
1604A - Era
555B - Case of Fugitive
551A - GukiZ and Contest
1399F - Yet Another Segments Subset
1371C - A Cookie for You
430B - Balls Game
1263A - Sweet Problem
1332B - Composite Coloring
254A - Cards with Numbers
215A - Bicycle Chain
1288B - Yet Another Meme Problem
1201C - Maximum Median
435A - Queue on Bus Stop
1409B - Minimum Product