出ました。
250
N個のパンケーキがあり、i番目のパンケーキの幅はi+1で美味しさはd[i]です。以下のような操作をしてタワーを作ります。
- 残っているパンケーキをランダムに１つ選びます。（残っていなければ終了）
- そのパンケーキの幅がタワーの一番上のパンケーキの幅より大きければ終了
- そうでないなら積んで、最初に戻る
タワーに積まれたパンケーキの美味しさの和の期待値を求めよ。
解法
期待値の線形性を使う。
つまり「Σ d[i] * (i番目のパンケーキが使われる確率)」で答えを求める。
dp[i][j] = i個のパンケーキを既に使っていて、一番上のパンケーキの幅がjである確率
というDPをして、答えは「Σ dp[i][j]*d[j]」で求めるといい。
初期化は、番兵をおいて、dp[0][N]とすると楽。
ちなみに遷移は、
if (k < j) dp[i+1][k] += dp[i][j]*(N-i)
みたいな感じ？
500
長さNのパーミュテーションであって、pos[i]の箇所だけp[i]<p[i+1]でそれ以外はp[i]>p[i+1]であるようなものを数え上げよ。
※ len(pos) = Mとします。
- N ≦ 10^6
- M ≦ 2500
解法
包除原理
まず、「posのところの条件を満たす必要がない」という問題を考えます。
単調減少でなければならない区間がM+1個出てきますよね。i個目の区間の長さをa[i]とします。
「posのところの条件を満たす必要がない」という問題の答えは「N!/mul(a[i]!)」です。
では、「posのところの条件を少なくともk個満たさない」という問題を考えます。
これは、
dp[i][j] = i番目の区間までを見て今までで少なくともj個の条件を満たさないものの個数/N!（i=0~M,j=0~M）
みたいなDPを考えるとできます。
「/N!」とかいてありますが、これは計算を簡略化するための工夫で、最後に*N!をするという感じです。
遷移は
dp[i][j] = Σ dp[i-k][j+k]*(Σa[i-k]~a[i])!
みたいな感じです（適当に書いたので細かい±1とかがずれてるかもしれませんが）
で、包除原理を使って答えを求めます。
このままだと３乗ですが、包除原理においては満たす条件の個数はどうでもよくて、その偶奇だけに興味があるので、dp[M][2]のDPにすると２乗になります。
ちなみに、さらにまとめてdp[M]（dp[i][0]-dp[i][1]を記録する）にしても良いです。
雑な解説なので、足りないところがあれば考えてみるか、聞いてください。
（本番では階乗の配列を2505で取ってて落ちました。つらい）
