Z algorithmを図に頼らずに理解したかったので書きました． 長さの文字列にZ algorithmを適用することを考えます． 以下の説明では文字列中の各文字を0-basedで指定します1．の文字目をと表記します．また，の文字目から文字目までを取り出した部分文字列を…

AtCoderのコンテストに参加するときの環境 (2024/03/15 現在) OS: Ubuntu 22.04 LTS エディタ: Visual Studio Code 拡張機能: rust-analyzer等 使用言語: Rust 自動化ツール: cargo-compete テンプレート use proconio::input; fn main() { input! { } } テ…

トリボナッチ数列の計算*1 フィボナッチ数列に類似した数列にトリボナッチ数列があります．フィボナッチ数列は最初の2項を初期値とし，3項目以降を直前の2項の和として定めていますが，トリボナッチ数列は最初の3項を初期値とし，4項目以降を直前の3項の和と…

多次元累積和を用いて多次元配列の矩形範囲の総和を計算するときに必要になったので，包除原理の拡張を考えました． 全体集合の個の部分集合と写像を考えます． このとき，和集合の全ての要素のによる像の総和について次の等式が成り立ちます． のとき，和集…