底とmodが互いに素でない離散対数問題

離散対数問題とは 整数 に対して, を満たす最小の非負整数 を求める問題です. 例えば のとき, より が解となります. Baby-step Giant-stepアルゴリズム 底 と mod が互いに素なときに使える離散対数問題の 解法です. とします. とおくと, となります. したが…

清一色のシャンテン数を01BFSで計算する

概要 清一色のシャンテン数は01BFSで計算できる。 機械的な計算なので、正当性が簡単に証明できる。 シャンテン数とは テンパイするまでに必要な牌の最小枚数のこと。 例えば のとき、 を引いてを捨てればテンパイとなる。これより少ない枚数の入れ替えでテ…

数列比較のRolling Hashは危険だよという話

概要 mod Rolling Hash が任意の基数で落ちる(数列比較の)問題が作れた。 基数を2つとってハッシュのペアで比較するか、もっと大きいmodを使おう。 Rolling Hashとは 文字列や整数列に対するハッシュ関数の一つ。以下では整数列のみを扱う。 法 と基数 を…

clion-live-templates-generator をリリースした

TL;DR 競技プログラミングのライブラリから、CLionのスニペット機能である「ライブラリテンプレート」の設定ファイルを生成してくれるパッケージを公開しました。 github.com 使い方 ローカルで使う 既にライブラリテンプレートを設定している場合は、上書き…

高速フーリエ変換を図で理解する

問題 次多項式 について、 での値を計算したい。 (※ ただし とおいた。) 愚直に計算するとかかるが、これをで計算する方法を考える。 アルゴリズム 簡単のため、以降 をの冪乗とする。 次多項式 を以下で定義する。 すると、 が成り立つ。 今 での の値を…

MacBookのJISキーボードをUSに設定する

概要 MacBookのJIS配列のキーボードをUS配列に設定します. 具体的には, 英数入力時, 記号だけUS配列に対応させる. ` と ~ は対応するキーがないので, deleteの一つ左にあるキーに割り当てる. 環境 macOS Catalina 10.15.4 手順 1. 入力ソースの設定 システム…

AtCoder頻出?貼るだけ高速ゼータ・メビウス変換&約数拡張

定義 高速ゼータ変換 例題 高速メビウス変換 約数に拡張した高速メビウス変換 例題 参考 定義 有限集合 , (可換な)半群 について, 写像 , が を満たすときを考える. (※ の形をしたものもあるが, と定義すれば前者と同じ形になるので割愛する.) 高速ゼータ…