1. 概要 本記事では，競技プログラミング（あるいは AtCoder Algorithm Lectures）での使用頻度が高い，代数構造に関する用語および，その代表例について解説します． 代数構造は典型的には，集合と集合上の演算の組として定義されます．例えば，整数に対す…

1. 概要 本記事では長さ $2 ^ N$ の列の XOR 畳み込みを求める問題を扱います． この問題は，整数列や実数列を対象とするような通常の状況では，Walsh-Hadamard 変換を用いて $\mathrm{O}(N\cdot 2 ^ N)$ 時間で求めることができます． Walsh-Hadamard 変換…

1. 概要 本記事では合同式の基礎的な考え方について説明します． 合同式は，整数全体を $m$ で割ったときの余り（剰余）に応じて分類するものです．競技プログラミングでは特に「答えを $m$ で割った余りで出力せよ」という形式が頻出で，そのような問題では…