【CF 908D】New Year and Arbitrary Arrangement

洛谷連結

題目描述

給定三個數k,pa,pb

每次有 p a p a + p b \frac{pa}{pa+pb} pa+pbpa​​ 的機率往後面添加一個 a a a

每次有 p b p a + p b \frac{pb}{pa+pb} pa+pbpb​ 的機率往後面添加一個 b b b

當出現了K個形如ab的子序列（不用連續）時停止

求最後子序列 ab 個數的期望

Sol

首先我們假設有長度限制,設 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示第到 i i i個字元已經有了 j j j個 a a a和 k k k個 a b ab ab的到最後停止的期望答案

最後答案即為 f [ 0 ] [ 0 ] [ 0 ] f[0][0][0] f[0][0][0]

假設加a和b的機率就是 pa 和 pb

轉移:

f [ i ] [ j ] [ k ] = p a ∗ f [ i + 1 ] [ j + 1 ] [ k ] + p b ∗ f [ i + 1 ] [ j ] [ j + k ] f[i][j][k]=pa*f[i+1][j+1][k]+pb*f[i+1][j][j+k] f[i][j][k]=pa∗f[i+1][j+1][k]+pb∗f[i+1][j][j+k]

當 j + k j+k j+k大于 K K K 的時候後面一部分可以直接統計答案了

但是如果沒有串長限制這樣下去就沒完沒了了 , 主要不好處理的是一下兩種情況:

1. 一直放 b , 這樣就無限轉移了
2. 一直放 a , 這樣也沒完沒了

對于情況1 , 我們可以先強制放一個 a 這樣其實一開始就會有 pa 的機率

然後由于前面的 b 不影響期望的權值 , 是以我們可在計算完答案後再來考慮

對于情況 2 , 我們發現如果 j + k j+k j+k 已經大于 K 了的話,那麼放一個 b 就會停止

可以把式子不斷遞歸化下去 , 根據我們的極限知識和無窮遞減等比數列求和公式,最後式子變成了這個(注意這時i沒有意義了,由于是倒推,做到了不重不漏):

f [ j ] [ k ] = ( i + j ) + p a p b f[j][k]=(i+j)+\frac{pa}{pb} f[j][k]=(i+j)+pbpa​

這樣就可以算了

在回到開頭一段有一堆 b 的情況 , 假設我們強制第一個是 a 的期望是 E E E,那麼最後的答案 E a n s = p a ∗ E + p b ∗ p a ∗ E + p b 2 ∗ p a ∗ E + . . . . . . . E_{ans}=pa*E+pb*pa*E+pb^2*pa*E+....... Eans​=pa∗E+pb∗pa∗E+pb2∗pa∗E+.......

繼續遞降無窮等比數列求和:

E a n s = E E_{ans}= E Eans​=E

是以不要管開頭的 b

(應該也可以通過期望的線性性來了解)

代碼:

#include<bits/stdc++.h>
using namespace std;
int k,pa,pb;
const int mod=1e9+7;
const int N=1001;
inline int fpow(int x,int k)
{
	register int res=1;
	while(k){
		if(k&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;k>>=1;
	}
	return res;
}
int f[N][N];
int D;
int dfs(int i,int j)
{
	if(i+j>=k) return f[i][j]=(i+j+D)%mod;
	if(f[i][j]!=0) return f[i][j];
	f[i][j]=1ll*pa*dfs(i+1,j)%mod+1ll*pb*dfs(i,i+j)%mod;
	f[i][j]%=mod;
	return f[i][j];
}
int main()
{
	scanf("%d %d %d",&k,&pa,&pb);
	register int inv=fpow(pa+pb,mod-2);
	pa=1ll*pa*inv%mod;pb=1ll*pb*inv%mod;
	D=1ll*pa*fpow(pb,mod-2)%mod;
	dfs(1,0);
	printf("%lld\n",1ll*f[1][0]%mod);
}