[CodeForces]908D New Year and Arbitrary Arrangement

设状态f[i][j]表示有i个a，j个ab的期望

发现如果i+j>=k的话就再来一个b就行了。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int mod=1e9++;

int k,pa,pb,inva,invb,f[][];

int ksm(int d,int z) {

    int res=;

    while(z) {

        if(z&) res=(1ll*res*d)%mod;

        d=(1ll*d*d)%mod;

        z>>=;

    }

    return res;

}

int main() {

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

    int tp=ksm(pa+pb,mod-);

    pa=1ll*pa*tp%mod,pb=1ll*pb*tp%mod;

    invb=ksm(pb,mod-);

    for(int i=k;i;i--) {

        for(int j=k;~j;j--) {

            if(i+j>=k) {f[i][j]=(1ll*i+1ll*j+1ll*pa*invb)%mod;continue;}

            f[i][j]=(1ll*f[i+][j]*pa+1ll*f[i][j+i]*pb)%mod;

        }

    }

    cout<<f[][];

    return ;

}

New Year and Arbitrary Arrangement