【CF908D】New Year and Arbitrary Arrangement

心已赠人 2023-08-17 15:48 120阅读 0赞

# Problem #

## Description ##

给定三个数 \\(k,pa,pb\\) ，每次有 \\(\\frac\{pa\}\{pa+pb\}\\) 的概率往后面添加一个 `a`，有 \\(\\frac\{pb\}\{pa+pb\}\\) 的概率往后面添加一个 `b` ，当出现了 \\(k\\) 个形如 `ab` 的子序列（不用连续）时停止。

求最后子序列 `ab` 的期望个数。

答案对 \\(10^9+7\\) 取模。

## Sample ##

### Input 1 ###

1 1 1

### Output 1 ###

### Input 2 ###

3 1 4

### Output 2 ###

370000006

## Range ##

\\(k\\le1000,p\_a,p\_b\\le10^6\\)

# Algorithm #

\\(DP\\)，概率与期望

# Mentality #

设 \\(f\_\{i,j\}\\) 表示当前有 \\(i\\) 个 \\(a\\) ，\\(j\\) 个子序列 \\(ab\\) ，在整个序列结束时的子序列 \\(ab\\) 的期望个数。发现第一维可能无限大，考虑倒推。

\\(f\_\{i,j\}\\) 的转移有两种情况，一是在末尾加入 \\(a\\) ，转移至 \\(f\_\{i+1,j\}\\) ，而是加入 \\(b\\) 转移至 \\(f\_\{i,j+i\}\\) 。那么倒推的方程就很明显了：  
\\\[ f\_\{i,j\}=\\frac\{p\_a\}\{p\_a+p\_b\}f\_\{i+1,j\}+\\frac\{p\_b\}\{p\_a+p\_b\}f\_\{i,j+1\} \\\]  
不过第一维无限大的问题还是没解决，必须考虑边界的问题。

我们发现，当 \\(i+j\\ge k\\) 的时候，如果我们加入 \\(b\\) ，则整个串就会立即终止。

那么对于一个状态 \\(f\_\{i,j\},(i+j\\ge k)\\) 来说，设在此状态上连续加入 \\(x\\) 个 \\(a\\) 再加入一个 \\(b\\) ，则：  
\\\[ f\_\{i,j\}=\\frac\{p\_b\}\{p\_a+p\_b\}\\sum\_\{x=0\}^\\infty(i+j+x)(\\frac\{p\_a\}\{p\_a+p\_b\})^x \\\]  
这是一个等比数列，那么我们直接等比数列求和就好了。

算出来得到：  
\\\[ f\_\{i,j\}=i+j+\\frac\{p\_a\}\{p\_b\} \\\]  
直接记搜就星了。

# Code #

#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <vector> using namespace std; long long read() { long long x = 0, w = 1; char ch = getchar(); while (!isdigit(ch)) w = ch == '-' ? -1 : 1, ch = getchar(); while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x * w; } const int Max_n = 1e3 + 5, mod = 1e9 + 7; int n, a, b; int pa, pb, pp; int f[Max_n][Max_n]; int ksm(int a, int b) { int res = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod; return res; } int DP(int a, int ab) { int &res = f[a][ab]; if (res != -1) return res; if (a + ab >= n) { res = (a + ab + pp) % mod; return res; } return res = (1ll * pa * DP(a + 1, ab) % mod + 1ll * pb * DP(a, ab + a) % mod) % mod; } int main() { #ifndef ONLINE_JUDGE freopen("D.in", "r", stdin); freopen("D.out", "w", stdout); #endif n = read(), a = read(), b = read(); pa = 1ll * a * ksm(a + b, mod - 2) % mod; pb = 1ll * b * ksm(a + b, mod - 2) % mod; pp = 1ll * a * ksm(b, mod - 2) % mod; memset(f, -1, sizeof(f)); printf("%d\n", DP(1, 0)); }

转载于:https://www.cnblogs.com/luoshuitianyi/p/11442403.html