FよりEの方がずっと難しい…。
https://atcoder.jp/contests/arc132/tasks/arc132_e
問題
N個のマスが左右1列に並んでおり、一部のマスには左向きまたは右向きのマークがついている。
この状態で、以下を繰り返す。
- マークがついていないマスを1つ等確率で選び、猫をそこに配置する。その後、左右どちらかを1/2の確率で選択して、その向きに猫を動かす。
- 別のマークがついてないマスか、両端に到達するまで猫は移動し続ける。その際、既存のマークは猫の移動方向に上書きされる。
- もし猫が別のマークがついてないマスに到着したら、まだ1/2の確率で左右どちらかに移動する
- 猫が端に到達した場合、1行目に戻る
全マスにマークがついた時、左向きのマークとなるマス数の期待値を求めよ。
解法
細かい証明はおいておいて解き方だけ。
最終的には、マス目は以下の形になる
<<<<(左向きで上書き)<<<<....(元のまま)....>>>>>(右向きで上書き)>>>>
マークのついてないマスで領域を区切ったとき、それぞれの領域が元のままである確率を求められれば、その時左向きのマークがついたマス数の期待値が求められる。
初期状態でマークのついてないマスがk個あるとする。
L(x)を、x個マークのついてないマスがあるとき、それら全部が左向きになるような猫の配置・移動経路選択の組み合わせとする。
R(x)を、同じく右向きのケースとする。L(x)=R(x)なのは自明。
ここで、L(x)=L(x-1)*(2x-1)となる。
左にx個、右に(k-x)個マークのついてないマスがある領域でできる猫の配置・移動経路選択の手順は、L(x)*R(k-x)*Binom(k,x)となる。
猫の初期配置と移動経路は、全部で2K!!通りあるので、(手順数)×(左向きマスの数)の総和をこれで割ることで期待値を算出できる。
int N; string S; const ll mo=998244353; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } ll L[202020]; ll comb(ll N_, ll C_) { const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==0) { inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; } if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>S; vector<pair<int,int>> V={{0,0}}; vector<int> sum={0,0}; FORR(s,S) { if(s=='<') V.back().first++,sum.back()++; if(s=='>') V.back().second++,sum.back()++; if(s=='.') { V.push_back({0,0}); sum.push_back(sum.back()); } } L[0]=1; for(i=1;i<=200000;i++) L[i]=L[i-1]*(2*i-1)%mo; ll ret=0; FOR(i,V.size()) { x=i; y=V.size()-(i+1); ll pat=L[x]*L[y]%mo*comb(x+y,y)%mo; (ret+=(sum[i]+i+V[i].first)*pat)%=mo; } for(i=1;i<=V.size()-1;i++) ret=ret*modpow(2*i)%mo; cout<<ret<<endl; }
まとめ
L(x)の漸化式や総数の計算がすんなりできないなぁ。