M-SOLUTIONS プロコンオープン C - Best-of-(2n-1)
問題のリンク
考察
期待値DPがしたい
E[i][j] := 高橋くんがi 回、青木くんがj 回勝っている状態からどちらかがN回勝つまでに行われるゲームの回数の期待値。
とすると、期待値DPの通常の手続きで解ける、がO(N ) は通らない。
タイトルに注目
どうにかして次元を削減しようと考えつつ、ふとタイトルを見てみると、高橋くんと青木くんが勝つ回数の和は最大で2N - 1 であることに気づく。
上と同じ手続きで、E(i) := 高橋くんと青木くんが合わせてi 回勝っている状況から、二人が合わせて2N - 1 回勝つまでに行われるゲームの回数の期待値。は求められる。これは少し都合の良いように変更すると、
E(i) := 二人が合わせて2N - 1 - i 回勝つまでに行われるゲームの回数の期待値。となり、具体的な式は、
(これはいつもの期待値DPのようにメモ化再帰で解く必要もない、簡単に解ける漸化式になってしまった。)
さて、二人が合わせてX 回勝つまでに行われるゲームの回数の期待値が求まると、N <= X <= 2N - 1 の範囲で、X 回目に高橋くん(青木くん)が勝利し、ゲームが終了する確率を求めることができればオッケーなことがわかる(期待値の線形性?)。
X回目に高橋くんが勝利し、ゲームが終了するという確率は、
となるので、求めるものは結局、
実装
#include <iostream> #include <algorithm> #include <vector> #define rep(i,n) for(int i=0;i<n;++i) #define rep1(i,n) for(int i=1;i<=n;++i) using namespace std; template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; } typedef long long ll; const ll MOD=1e+9+7; struct mint{ ll x; mint(ll x=0):x(x%MOD){} mint& operator+=(const mint a){ if((x+=a.x)>=MOD) x-=MOD; return *this; } mint& operator-=(const mint a){ if((x += MOD-a.x)>=MOD) x-=MOD; return *this; } mint& operator*=(const mint a){ (x*=a.x)%=MOD; return *this; } mint operator+(const mint a) const{ mint res(*this); return res+=a; } mint operator-(const mint a) const{ mint res(*this); return res-=a; } mint operator*(const mint a) const{ mint res(*this); return res*=a; } mint pow(ll t) const{ if(!t) return 1; mint a = pow(t>>1); a*=a; if(t&1) a*=*this; return a; } //for prime mod mint inv() const{ return pow(MOD-2); } mint& operator/=(const mint a){ return (*this) *= a.inv(); } mint operator/(const mint a) const{ mint res(*this); return res/=a; } }; const int NMAX=200010; // we can calculate nCk until n is equal to NMAX mint fact[NMAX],infac[NMAX]; void Make_Fact(){ fact[0]=fact[1]=1; for(int i=2;i<=NMAX-1;++i){ fact[i]=fact[i-1]*(mint)i; } } void Make_InvFact(){ infac[0]=infac[1]=1; for(int i=2;i<=NMAX-1;++i){ infac[i]=infac[i-1]/(mint)i; } } mint Comb(int n,int k){ if(n<0||k<0||n-k<0) return 0; return fact[n]*infac[k]*infac[n-k]; } vector<mint> dp; vector<bool> flag; int main() { int n; cin >> n; int a,b,c; cin >> a >> b >> c; dp.resize(2*n); flag.resize(2*n, false); flag[2*n - 1] = true; vector<mint> apow(n+1), bpow(n+1); apow[0].x = 1; bpow[0].x = 1; rep(i,n) apow[i+1] = apow[i] * (mint)a / (mint)(a+b); rep(i,n) bpow[i+1] = bpow[i] * (mint)b / (mint)(a+b); auto rec = [&](auto f, int i) { if(flag[i]) return dp[i]; flag[i] = true; mint res = (mint)100 + (mint)(a+b) * f(f, i+1); res /= (mint)(100 - c); return dp[i] = res; }; Make_Fact(); Make_InvFact(); rec(rec, 0); mint res = 0; for(int i = 0; i < n; ++i) { res += dp[i] * apow[n] * bpow[n-1-i] * Comb(2*n-i-2, n-1); res += dp[i] * apow[n-1-i] * bpow[n] * Comb(2*n-i-2, n-1); } cout << res.x << "\n"; return 0; }