高速ゼータ変換について，自分用にまとめた記事です．

AtCoder Regular Contest 137 D - Prefix XORs の解法です． コンテスト中に解いた方法 (実験結果から適当に求める) をベースに， 公式解説を参照して追加しました． リュカの定理の証明もWikipediaを見て書きました． 問題概要 長さ$N$の整数列 $A = (A_1, \ldots, A_N)$ と整数 $M$ が与えられる． 下の操作を$k$回行ったあとの $A_i$ の値を $A(i, k)$ と書くことにする． $k = 1, 2, \ldots, M$ について，$A(N, k)$ を求めよ． 操作: 各$i = 1, 2, \ldots, N$ について， $A_i$ を同時に $A_1 \oplus A_2 \oplus \cdots \oplus A_i$ で置き換える． 制約: $1 \leq N, M \leq 10^6$; $0 \leq A_i < 2^{30}$ 問題へのリンク 解法 実験 $A(i, k)$ は，$A_1, \ldots, A_i$ のいくつかのXORをとったものになる． そこで，$a(i, m, k) \in \{0, 1\}$ をとって， $A(i, k) = \bigoplus_{m=1}^{i} a(i,m,k) A_m$ と書く． 計算してみると分かるとおり，$a(i, m, k)$ は，$i - m$ と $k$ にしか 依存しない．そこで，$b(j, k) := a(j, 0, k)$ と書くことにする． $A(i, k) = \bigoplus_{m=1}^{i} b(i - m, k) A_m = \bigoplus \{ A_{i - j} \mid b(j, k) = 1; j = 0, \ldots, i-1 \}$ だから， 各 $k = 1, 2, \ldots, M$ について，$b(j, k) = 1$ となる $j$ を (高速に) 列挙できれば良い．...

解説ACです．

解説ACです

解説ACです．

最大流と最小カットについてのコンテスト用のまとめです

ABC238G Cubic? の解法です．公式解説と同じです．

素因数分解に要する時間を，事前計算と個別の計算に分けて計測しました

方針にも実装にも時間がかかりました．

パナソニックプログラミングコンテスト2021に参加して，ABCDEF 6完347位でした．A - Water Pressure / B - Election / C - Counting 2 / D - Neighbors / E - Minimal payments / F - Jealous Two

解説ACです．

ABC228 (トヨタシステムズプログラミングコンテスト2021 AtCoder Beginner Contest 228) に参加して ABCDE5完 265位でした．A - On and Off / B - Takahashi’s Secret / C - Final Day / D - Linear Probing / E - Integer Sequence Fair / F - Stamp Game

ABC226 に参加して，ABCDE5完 922位でした．冷えました． A - Round decimals; B - Counting Arrays; C - Martial artist; D - Teleportation; E - Just one; F - Score of Permutations

解法です．公式解説ほぼそのままです．

AtCoder Beginner Contest 225 (ABC225) に参加して，ABCD 4完の 1004 位でした．冷えました．A - Distinct Strings / B - Star or Not / C - Calendar Validator / D - Play Train / E - フ