今日のCFは良いとこ無し…。
Codeforces #736 Div1B. Integers Have Friends
問題自体としては No.1036 Make One With GCD 2 - yukicoder が近い。
区間GCD がセグ木で計算できることは知っていたが SWAG(未履修) を用いて求めることができるのは初耳だった。
lorent さんの実装をガン見…(ありがとうございました)
Binary GCD
除算処理を介さずに GCD が計算できると…嬉しい！
方針としては次の通り。$x, y$ を自然数として $\gcd(x,y)$ を計算することを考える。
$x, y$ が共に奇数になるまで $2$ で割りつつ、$\gcd(x,y)$ が素因数として $2$ を何個持つか求める。
$x \leq y$ として、$y := y-x$ と代入する。$x, y$ は共に奇数であったから、今 $y$ は偶数になっているので、$2$ で繰り返し割って奇数にする(ただし $y \gt 0$)。
$y = 0$ になるまで上の操作を繰り返す。
残った $ x $ に最初求めた2ベキを掛けることで GCD が求まる。
__builtin_ctz 等を使うと簡潔に書ける。0 の場合は未定義なので予め場合分けで除いておく。
Sliding Window Aggregation
熨斗さんによる日本語記事が分かりやすかったです。ありがとうございます。
stack で次の操作をならし計算量*1 $O(1)$ で処理することを考える。
- pop()
stackの末尾の要素を1つ削除する
- push($ x $)
stackの末尾に $ x $ を1つ追加する
- fold()
stack内の要素の総積を計算する
これは要素の他に累積積も保持しておくことで達成できる。
この応用として、queue の操作を stack 2つでシミュレーションすることを組み合わせたのが SWAG と認識しています。
総積を計算する時は、2つの stack の末尾の積を計算すれば queue 全体の積が計算できる。
1つの要素が push, pop される回数を考えると、償却 $O(1)$ が言える。
まだ詳しく分かってないこと
dequeも同様にstack2つで表すことができるらしい- SWAG で扱うことのできる半群に対する理解
Codeforces #736 Div1C. The Three Little Pigs
まず、$ i $ 日目に $ m $ 匹を選ぶ方法は $(1 + x) ^ {3 i}$ の $x^{m}$ の係数に一致する。
$1 \leq i \leq n$ についての総和が知りたいので、$f = (1 + x) ^ {3}$ とおいて、
$$ f + f^{2} + \ldots + f^{n} = \frac{f^{ n + 1 } - f }{f - 1} $$
の $x^{m}$ の係数が分かれば良い。
右辺の分子は $ x $ の $3(n+1)$ 次式であり、分母は $3$ 次式であるから多項式の割り算が線形時間で出来る。
前計算としてこの多項式を求めれば、後はクエリに対して $O(1)$ で答えられる。
*1:多分 計算量周りの記述は怪しめです
