近いところまで考察できていたのに、詰め切れず…。
https://atcoder.jp/contests/abc238/tasks/abc238_h
問題
N人の人が距離1ずつ離れて等間隔で円環状に並んでいる。
各人時計回りか反時計回りいずれかを向いており、その向きは入力として与えられる。
以下の処理を行うとき、手順はN!通りあるが、コストの総和の期待値を求めよ。
- 残った人が2人以上いる場合、そのうちだれかを等確率で選ぶ。
- 選んだ人の向いている向きの先にいる最寄りの人を取り除く。
- その際、取り除いた人までの距離をコストとする。
解法
人を取り除く手順を考えると、同じ人が複数回選ばれたりしてややこしい。
逆に、1人の状態から巻き戻すことを考えよう。
以下の2関数を考える。なお、人の番号は適宜Nで割った余りで考えると楽。
f(L,R) := L番とR番の人が円環状に配置済みで、その間に人がいないような状態に対する、その後の中の人の埋め方の組み合わせ
g(L,R) := (同上)な状態に対する、その後の中の人の埋め方におけるコストの総和
最後に残る人xを総当たりし、g(x,x+N)の総和を取ってN!で割れば解となる。
あとはf(L,R)とg(L,R)を求めよう。
- L+1=Rなら、間に人はいないのでf(L,R)=1, g(L,R)=0
- そうでない場合、次に埋まる人Mを総当たりする。MはL番とR番どちらの人に消されるかを考えると、
- M番がL番とR番どちらに消されうるかをc通り、それぞれのコストの総和をdとすると、以下で計算できる。
- f(L,R) += f(L,M)*f(M,R)*c*Comb(R-L-2, M-L-1)
- g(L,R) += (f(L,M)*f(M,R)*d + c*(f(L,M)*g(M,R) + g(L,M)*f(M,R)))*Comb(R-L-2, M-L-1)
int N; string S; const ll mo=998244353; const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; 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 comb(ll N_, ll C_) { if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);} ll pat[603][603]; ll sum[603][603]; ll dfs(int L,int R) { if(pat[L][R]>=0) { return sum[L][R]; } ll& p=pat[L][R]; ll& s=sum[L][R]; p=s=0; if(L+1==R) { p=1; } else { for(int M=L+1;M<R;M++) { int pa=(S[L]=='R')+(S[R]=='L'); int co=(S[L]=='R'?M-L:0)+(S[R]=='L'?R-M:0); dfs(L,M); dfs(M,R); (p+=pat[L][M]*pat[M][R]*pa%mo*comb(R-L-2,M-L-1))%=mo; (s+=(pat[L][M]*pat[M][R]%mo*co+pa*pat[L][M]*sum[M][R]+pa*sum[L][M]*pat[M][R])%mo*comb(R-L-2,M-L-1))%=mo; } } return s; } void solve() { int i,j,k,l,r,x,y; string s; 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; cin>>N>>S; S+=S; MINUS(pat); ll ret=0; FOR(x,N) ret+=dfs(x,x+N); ret=ret%mo*factr[N]%mo; cout<<ret<<endl; }
まとめ
逆順に巻き戻すことも、間を埋めることも考えられたのに、その際の組み合わせ計算を詰め切れなかったのが残念。