<style> /* basic design */ .reveal h1, .reveal h2, .reveal h3, .reveal h4, .reveal h5, .reveal h6, .reveal section, .reveal table, .reveal li, .reveal blockquote, .reveal th, .reveal td, .reveal p { text-align: left; line-height: 1.8; letter-spacing: normal; text-shadow: none; word-wrap: break-word; color: #444; } .reveal h1, .reveal h2, .reveal h3, .reveal h4, .reveal h5, .reveal h6 {font-weight: bold;} .reveal th {background: #DDD;} .reveal section img {background:none; border:none; box-shadow:none; max-width: 95%; max-height: 95%;} .reveal blockquote {width: 90%; padding: 0.5vw 3.0vw;} .reveal table {margin: 1.0vw auto;} .reveal code {line-height: 1.2;} .reveal p, .reveal li {padding: 0vw; margin: 0vw;} .reveal .box {margin: -0.5vw 1.5vw 2.0vw -1.5vw; padding: 0.5vw 1.5vw 0.5vw 1.5vw; background: #EEE; border-radius: 1.5vw;} /* table design */ .reveal table {background: #f5f5f5;} .reveal th {background: #444; color: #fff;} .reveal td {position: relative; transition: all 300ms;} .reveal tbody:hover td { color: transparent; text-shadow: 0 0 3px #aaa;} .reveal tbody:hover tr:hover td {color: #444; text-shadow: 0 1px 0 #fff;} /* blockquote design */ .reveal blockquote { width: 90%; padding: 0.5vw 0 0.5vw 6.0vw; font-style: italic; background: #f5f5f5; } .reveal blockquote:before{ position: absolute; top: 0.1vw; left: 1vw; content: "\f10d"; font-family: FontAwesome; color: #2980b9; font-size: 3.0vw; } /* font size */ .reveal h1 {font-size: 5.0vw;} .reveal h2 {font-size: 4.0vw;} .reveal h3 {font-size: 2.8vw;} .reveal h4 {font-size: 2.6vw;} .reveal h5 {font-size: 2.4vw;} .reveal h6 {font-size: 2.2vw;} .reveal section, .reveal table, .reveal li, .reveal blockquote, .reveal th, .reveal td, .reveal p {font-size: 2.2vw;} .reveal code {font-size: 1.6vw;} /* new color */ .red {color: #EE6557;} .blue {color: #16A6B6;} /* split slide */ #right {left: -18.33%; text-align: left; float: left; width: 50%; z-index: -10;} #left {left: 31.25%; text-align: left; float: left; width: 50%; z-index: -10;} </style> <!-- --------------------------------------------------------------------------------------- --> <br><br><br> # <div style="text-align: center;">ABC178 D Leaping Tak</div> ### <div style="text-align: center;">@reyu </div> --- ## 問題 https://atcoder.jp/contests/abc179/tasks/abc179_d  --- ## ざっくりと #### 問題文 $S$ が $K$ 個の区間の和集合として与えられる 高橋くんは $d \in S$ であるとき正の方向に $d$ マス移動できる $N$ マス目にちょうど着くような行き方の個数をmodで割った余りを求めてください #### 制約 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq K \leq 10$ --- ## 考えたこと - $O(N^2)$ は無理 - $N$ を分ける組み合わせを数学っぽく考えるのとかはやばそう - なんかこういう問題見たことあるな - DPじゃね？ --- ## DPな気がする とりあえず考えてみる #### 配るDP $0 \leq i \leq n-1$ でそれぞれ $d \in S$ を満たすすべての $d$ について, $dp[i+d]$ に $+dp[i]$ する $O(N|S|)$ <br> #### もらうDP $0 \leq i \leq n-1$ でそれぞれ $dp[i]=\displaystyle \sum_{d \in S} dp[i-d]$ (範囲外は0として考える) $O(N|S|)$ --- ## やばい 普通にやると $|S|=N$ とかで破滅します どうにかしましょう --- ## 考える(配る場合) 「 $d \in S$ を満たすすべての $d$ について, $dp[i+d]$ に $+dp[i]$ 」を速くしたい 問題文より, $d$ は $K$ 個の区間  $K$ 回の区間加算が高速にできればいけそう --- ## 区間加算といえば - imos法 ( $O(1)$ ) - 更新と出力が混ざってるとうまくいくか怪しい - 遅延評価セグメント木・区間加算対応BIT ( $O(\log N)$ ) - つよい --- ## imos法でできるか考える 配列imosが, $\displaystyle \sum_{j=0}^i imos[j]=dp[i]$ を満たすとする $dp[i]$ を単体で計算するには $O(i)$ $dp[i]$ がわかっているときに $dp[i+1]$ を計算するのは $O(1)$ 今回の場合だと, 下から考えていくことで $dp[i+1]$ を使うときはすでに $dp[i]$ が確定しているかつ計算されている 計算量は $O(NK)$ なので間に合いそう --- ## imos法の罠(?) 解説者はこれでコンテスト中10分ぐらい溶かしました 初期状態は $imos[0]=1$, $imos[1]=-1$ になる (それはそう) --- ## 考える(もらう場合) $dp[i]=\displaystyle \sum_{d \in S} dp[i-d]$ を速く計算したい  $K$ 回の区間和の計算が高速にできればうまくいきそう --- ## 区間和といえば - 累積和 ($O(1)$) - 更新と出力が混ざってるとうまくいくか怪しい - セグメント木・BIT ($O(\log N)$) - またお前らか --- ## 累積和でできるか考える 累積和が計算されてるところの値を更新すると計算し直さないといけない 更新されるのはもらうときだけ, $i$ でもらっているときに $i+1$ 以上のところの累積和が使われることはないので、もらった後に累積和を更新すれば大丈夫そう --- ## 実装 #### 配る imos法 : https://atcoder.jp/contests/abc179/submissions/16953329 BIT : https://atcoder.jp/contests/abc179/submissions/16954844 #### もらう 累積和 : https://atcoder.jp/contests/abc179/submissions/16955380 BIT : https://atcoder.jp/contests/abc179/submissions/16955353 --- ## 公式解説  --- ## ん？ > なお、遷移が少ない区間の和で表わせなくともこの制約の下で $O(N\log N)$ で解けることが知られています。 --- ## はい 形式的べき級数とやらでいい感じに解けるらしい #### 注意 - 解説者はよくわかっていません。実装もしてません。 - 雰囲気で話すのでやばそうだったら指摘してください。 - ここらへん見たほうが良いかも https://drken1215.hatenablog.com/entry/2020/09/20/081800 https://paper.dropbox.com/doc/1.-0TKPiV44tWPh4A8XKsBE8 https://codeforces.com/blog/entry/56422 --- # 準備 $v \in S$ であるとき $x^v$ の係数が1, そうでないなら0であるような多項式 $f$ を考える つまり, $f$ の $x_v$ の係数は, 1回の移動で $v$ マス目に行く行き方の数と一致する このとき, $f^n$ の $x^v$ の係数は、$n$ 回の移動で $v$ マス目に行く行き方の数と一致する つまり、$\displaystyle \sum_{k=0}^{\infty}f^k$ の $x^N$ の係数が求める答えとなる --- ## 形式的べき級数とは 多項式 $f$ について $\displaystyle \sum_{k=0}^\infty a_if^k$ みたいに表されるもの 和差積が定義できて、結合・交換・分配法則なども成り立つ 色々いい感じのことができる 例えばこのような変形ができる $\displaystyle \sum_{k=0}^{\infty}f^k \times f= \sum_{k=1}^{\infty}f^k=\sum_{k=0}^{\infty}f^k-1$ $\displaystyle \sum_{k=0}^{\infty}f^k(1-f)=1$ $\displaystyle \sum_{k=0}^{\infty}f^k=\frac{1}{1-f}$ --- ## つまり $\displaystyle \frac{1}{1-f}$ の $x^N$ の係数を考えれば良さそう $1-f$ の逆元的なものを考えたい --- ## f(x)の逆元を求める 多分逆元を求めるのは厳しい でも逆元の $N$ 項目までは $O(N \log N)$ で求められるらしい 前提 : $f(x) \equiv g(x)\ (mod\ x^n)$ のとき, $f(x)$ と $g(x)$ の $n+1$ 項目までは一致する $R_n(x)f(x) \equiv 1\ (mod\ x^n)$ を満たす $R_n(x)$ を考える $R_n(x)f(x)-1 \equiv 0\ (mod\ x^n)$ $(R_n(x)f(x)-1)^2 \equiv 0\ (mod\ x^{2n})$ $R_n(x)^2f(x)^2-2(R_n(x)f(x))+1 \equiv 0\ (mod\ x^{2n})$ $f(x)(2R_n(x)-R_n(x)^2f(x))\equiv 1\ (mod\ x^{2n})$ という感じに順番に計算できる --- ## これほんとに $O(N\log N)$ ? $N$ 項の多項式同士のかけ算は普通にやると $O(N^2)$ FFTを使うと $O(N \log N)$ でできる $T(N)=T(N/2) + O(N \log N) = O(N \log N)$ (らしい) --- ## 最後に - これ緑diffってまじ - またEと択でしたね (解説者はEで沼ったけどdiffはEのほうが低い)