AGC028-B：Removing Blocks

問題

https://beta.atcoder.jp/contests/agc028/tasks/agc028_b

考え方

難しすぎる。N! 通りの除く順番のうち、それぞれで A_i が何回加算されるか？がわかれば嬉しい。N! 通りの順番は当然シミュレーションできないので以下を考えることがこの問題を解くうえでのポイント。

「あるブロック j を除いたときに A_i が何回加算されるか」

j \le i とする。すべての j について、A_i の加算回数が求められれば嬉しい。ブロック j を除いたときに i が加算されるには、 i 番目から j 番目のブロックが残っている必要がある。よって j が一番最初に取り除かれなければならない。

j 番目のブロックを除いたときに、その他のブロックを除く順番は任意である。 k = j - i + 1 とすると、その他のブロックの並べ方は (k-1)! 通りである。また n 箇所から k 箇所選ぶ組み合わせの数は {}_n \mathrm{C} _k である。 k 以外のブロックの並べ方は任意であるから (n-k)! 通りである。よって

(k-1)! \times {}_n \mathrm{C} _k \times (n-k)! \displaystyle = \frac{n!}{k} = \frac{n!}{j-i+1}

通りである。j \gt i の場合も同様であることがわかるので、係数は \displaystyle \frac{n!}{|j-i|+1} となる。

それぞれの A_i について上記の係数をかけ合わせれば解が求められるのだが、上記は O(n) かかるのでこれを高速化する。実際に値を代入して確かめるとわかるが、この分子の値は以下のようになっている。

例として N=4 とする。

i=1 1 2 3 4
i=2 2 1 2 3
i=3 3 2 1 2
i=4 4 3 2 1

上記は 1 を基準に左右に等間隔で並んでいる。よって事前に累積和で

\displaystyle \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dotsb

を求めておけばそれぞれの i について O(1) で係数を求めることができる。mod 上の演算については逆元をとればよい。

Submission #3584050 - AtCoder Grand Contest 028

ポイント

  • ？？？

参考

雑記

一番最初のポイントを思いつくのが難しいし、modの逆元 + 累積和での高速化もバグりやすい。