AtCoder Grand Contest 028：B - Removing Blocks

問題
解法
解答

問題

解法

各ブロックについてそのブロックの重さが答えに加算される回数を求めたい．ブロック i の重さが加算される回数を求める．ブロック i とブロック j が連結である場合の数を P(i, j) とおく．P(i, j) (1 <= j <= N) の和がブロック i の重さが答えに加算される回数になる．

i <= j の下で考えると，ブロック i とブロック j が連結であるとき，区間 [j, i] のブロック (|i - j| + 1) 個は，どれも取り除かれていない．一方，それ以外の区間のブロック N - (|i - j| + 1) 個は，取り除かれていても取り除かれていなくてもどちらでもいい．ブロックを取り除く順番を {1, 2, 3, ..., N} の順列であらわすことにすると，区間 [j, i] のブロックの取り出し方は (j, {j + 1, j + 2, ... , i}) となり，この場合の数は (|i - j|)! となる．この取り出し方を長さ N の順列に当てはめるので，この場合の数は C(N, |i - j| + 1) となる．区間 [j, i] 以外のブロックの取り出し方の場合の数は (N - (|i - j| + 1))! となる．よって，P(i, j) は，式を整理して，

P(i, j) = (|i - j|)! * C(N, |i - j| + 1) * (N - (|i - j| + 1))! = N! / (|i - j| + 1)

となる．よって，j の位置は関係なく，区間 [j, i] の長さ (|i - j| + 1) が P(i, j) に関係すると分かる．

ここで，i によって (|i - j| + 1) が取る値の個数が変わってくる．具体的には，N = 6 のとき，(|i - j| + 1) の値は 1, 2, 3, 4, 5, 6 のどれかを取るが，j が変化することによってそれぞれの値が現れる回数を (a, b, c, d, e, f) 回とあらわすことにすると，

i = 1 のとき (1, 1, 1, 1, 1, 1) 回

i = 2 のとき (1, 2, 1, 1, 1, 0) 回

i = 3 のとき (1, 2, 2, 1, 0, 0) 回

i = 4 のとき (1, 2, 2, 1, 0, 0) 回

i = 5 のとき (1, 2, 1, 1, 1, 0) 回

i = 6 のとき (1, 1, 1, 1, 1, 1) 回

というように変化する．よく眺めるとこれには規則性があって，i が (i - 1) から変化するとき，i の値を取る回数が + 1 され，(N - (i - 1) + 1) の値を取る回数が - 1 される．

各ブロック i が答えに加算される回数は P(i, j) * ((|i - j| + 1) の値を取る回数) (1 <= j <= N) となり，答えは 1 <= i <= N について上の式を計算し，全て足したものになる．(|i - j| + 1) の値を取る回数は前に示した規則性より前計算 O(N) と遷移 O(1) で求められるので，全体で O(N)．mod の割り算があるので逆元を用いる．