問題 問題概要 与えられた漸化式によって導かれるM番目の値を求めよ. 解法 andとxorの演算は, (G, 和, 積) := ({1,0}, xor, and)とすると, 環をなしている. また, 行列の演算は半環であれば, 成り立つ. これらのことから, 通常の行列ライブラリの和をxorへ, …

問題 問題概要 1以上N以下の全ての数字のなかに数字1が全部でいくつ含まれているか? 解法 脳死しているので桁dpをする. dp[i][j][k] := i桁目まで見て, j==1ならNより小さい, 1を使った数がk回となる数字の総数 という状態を決めてやればいい. 漸化式の遷移…