AGC028-B:Removing Blocks
問題
https://beta.atcoder.jp/contests/agc028/tasks/agc028_b
考え方
難しすぎる。 通りの除く順番のうち、それぞれで が何回加算されるか?がわかれば嬉しい。 通りの順番は当然シミュレーションできないので以下を考えることがこの問題を解くうえでのポイント。
「あるブロック を除いたときに が何回加算されるか」
とする。すべての について、 の加算回数が求められれば嬉しい。ブロック を除いたときに が加算されるには、 番目から 番目のブロックが残っている必要がある。よって が一番最初に取り除かれなければならない。
番目のブロックを除いたときに、その他のブロックを除く順番は任意である。 とすると、その他のブロックの並べ方は 通りである。また 箇所から 箇所選ぶ組み合わせの数は である。 以外のブロックの並べ方は任意であるから 通りである。よって
通りである。 の場合も同様であることがわかるので、係数は となる。
それぞれの について上記の係数をかけ合わせれば解が求められるのだが、上記は かかるのでこれを高速化する。実際に値を代入して確かめるとわかるが、この分子の値は以下のようになっている。
例として とする。
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
を基準に左右に等間隔で並んでいる。よって事前に累積和で
を求めておけばそれぞれの について で係数を求めることができる。mod 上の演算については逆元をとればよい。
Submission #3584050 - AtCoder Grand Contest 028
ポイント
- ???
参考
- AGC028-B: Removing Blocks - 思考の墓場
- AGC028 参加記録&解説(A~C) - ARMERIA
- AtCoder Grand Contest 028 B - Removing Blocks - かねこの徒然日記
雑記
一番最初のポイントを思いつくのが難しいし、modの逆元 + 累積和での高速化もバグりやすい。