100가지 동적 계획 – 42 CodeForces 908D New Year and Original Order 확률 DP

Good Bye 2017!
확률DP는 진심으로할 수 없다...
k,pa,pb 하나 주세요.
처음에 현재 직렬은 빈 직렬로 매번 조작할 때pa/(pa+pb)의 확률로 현재 직렬에'a', pb/(oa+pb)의 확률에 문자 b를 추가한다. 현재 직렬의 하위 서열을 고려하면 k 하위 서열'ab'보다 크면 멈추고 이 때 하위 서열에서'ab'의 기대 출현 횟수를 묻는다.
정의 상태 dp[i][j]는 현재 열에 i 하위 서열'a'가 나타났을 때, j 하위 서열'ab'가 나타났을 때, 다시 계속하고, 마지막으로 멈췄을 때의 하위 서열'ab'가 나타날 수 있는 횟수를 나타낸다.
우선 고려해야 할 문제는 여기 i와 j는 관계가 없다는 것이다. 만약 이 점을 분명히 생각해야만 계속 아래를 볼 수 있다
원하는 정의에 따라 우리가 dp[i][j] 뒤에 a를 추가할 때 이동하는 상태는 dp[i+1][j]이고 b를 추가할 때 이동하는 상태는 dp[i][i+j]이다.
따라서 우리의 상태 이동 방정식은 다음과 같다.
dp[i][j]=pa/(pa+pb)*dp[i+1][j]+pb/(pa+pb)*dp[i][i+j]
우리의 초기 상태는 dp[i][j]=j 여기 i 마음대로 j>=k
우리의 마지막 상태는 dp[0][0], 즉 처음의 공백에 대응하는 것이다
하지만!
위의 상태 정의는 사실 두 가지 작은 문제가 있어요.
1. 우리가 방금 말했듯이 초기 상태 dp[i][j]=j는 여기에서 i가 자유롭다는 것은 사실상 문자 a가 무한히 부가될 수 있다는 것을 의미한다.그래서 우리는 dp[i][j]=j+i+pa/pb로 전환하여 여기 i+j>=k
우리가 보기에 이 식은 정의에 따라 dp[i][j]가 멈춘 후 ab에 나타난 기대에 따라 i+j>=k가 나타나기 때문에 b가 하나만 나타나면 멈춘다. 따라서 우리는 기하학적 분포의 기대를 사용한다. p/pb는 b가 처음 나타났을 때 a의 기대 출현 횟수를 대표하고 그 다음에 원래 i개의 a가 있기 때문에 마지막 ab의 수량은 i+j+pa/pb이다.
2. b는 첫 번째 a가 나타나기 전에 무한히 나타날 수 있기 때문에 우리는 최종 구해의 상태를 dp[1][0]로 설정한다.
3. 처음부터 파를 p*(pa+pb)^-1로 처리하고 pb를 pb*(pa+pb)^-1로 처리한 후 바로 이렇게 계산하면 된다
사실 코드가 짧아요.

#include 
#include 

using namespace std;
typedef long long ll;
const ll mod=1000000007,maxm=1010;

ll inv(ll a,ll b=mod),dp[maxm][maxm],pa,pb,k;
inline getdp(int i,int j){return j>=k?j:dp[i][j];}
void egcd(ll a,ll b,ll& d,ll& x,ll& y);

int main(){
    ios_base::sync_with_stdio(0);
    cin>>k>>pa>>pb;
    const ll pb_inv=inv(pb),_inv=inv(pa+pb),pa_new=(pa*_inv)%mod,pb_new=(pb*_inv)%mod;
    for(int j=0;j=0;--j)
        dp[i][j]=(pa_new*getdp(i+1,j)+pb_new*getdp(i,i+j))%mod;
    cout<