Codeforces 908D New Year and Arbitrary Arrangement（概率DP，边界条件处理）

题目链接 Goodbye 2017 Problem D

题意一个字符串开始，每次有$\frac{pa}{pa+pb}$的概率在后面加一个a，$\frac{pb}{pa+pb}$的概率在后面加一个$b$。

　　求当整个串中有至少$k$个$ab$的时候（不需要连续，下同），字符串中$ab$个数的期望。

设$f[i][j]$为字符串有$i$个$a$，$j$个$ab$的时候字符串中$ab$个数的期望

设$p = \frac{pa}{pa+pb}$, $q = \frac{pb}{pa+pb}$

那么对于正常的情况（非边界情况），

$f[i][j] = f[i+1][j] * p + f[i + 1][i + j] * q$

对于边界情况，即当$i + j >= k$且$j < k$的时候，这个时候再加一个$a$就满足了题意的条件。

这个情况下$f[i][j] - i - j$应该都是一样的。令$f[i][j] - i - j = c$。

$c = pq + 2p^{2}q + 3p^{3}q + ... + ...$

时间复杂度$O(n^{2})$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N   = 1e3 + 10;

const int mod = 1e9 + 7;

int f[N][N];

int k, pa, pb, A, B, C;

void gcd(int a, int b, int &x, int &y){

	if (!b) {x = 1; y = 0;}

	else { gcd(b, a % b, y, x); y -= x * (a / b);}

}

int inv(int a){

        int x, y;

        gcd(a, mod, x, y);

        return (x % mod + mod) % mod;

}

int main(){

	scanf("%d%d%d", &k, &pa, &pb);

	A = 1ll * pa * inv(pa + pb) % mod;

	B = (1 - A + mod) % mod;

	C = 1ll * pa * inv(pb) % mod;

	dec(i, k, 1){

		dec(j, k, 0){

			f[i][j] = i + j >= k ? (i + j + C) % mod: (1ll * A * f[i + 1][j] + 1ll * B * f[i][i + j]) % mod;

		}

	}

	printf("%d\n", f[1][0]);

	return 0;

}

巴特西

Codeforces 908D New Year and Arbitrary Arrangement（概率DP，边界条件处理）

最新文章

热门文章