anta1 https://blog.hatena.ne.jp/anta1/ antaの競技プログラミング練習日記 https://anta1.hatenadiary.org/ 作った問題 ※上手く書けなくて、途中から放棄してます http://d.hatena.ne.jp/anta1/20130118/1358492699で書いた、作った問題の想定解法です。詳細はその記事を参照してください。 問題概略 「ある位置にパスカルの三角形の最初の何段かをmod1000000007で足す」というクエリをO(段数)くらいで処理して、最後に全部出力せよ 想定解法 一般化した累積和の逆を用いる。 通常の累積和・その逆ではある一定方向に対する和・差を取る。 しかしそれでは、多項式でないと効率的な形にできない。 まず、パスカルの三角形に下のような辺を張ってみる。 ここで、辺の向きは下向きとする。 … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fanta1.hatenadiary.org%2Fentry%2F20130201%2F1359651597" title="作った問題「パスカルの三角形クエリ」の解法 - antaの競技プログラミング練習日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/a/anta1/20130201/20130201012238.jpg Hatena Blog https://hatena.blog 2013-02-01 01:59:57 rich https://anta1.hatenadiary.org/entry/20130201/1359651597 1.0 100%