問題のネタバレを多く含みます 挿入 DP 隣り合う項の大小関係に条件がついた順列を数え上げるときに使われることが多い。 $\mathrm{dp}(i, S) := $ $(1, 2, \dots, i$ からなる順列のうち、$S$ をみたすものの個数$)$ という状態を考えるのだが、遷移の考え…

AtCoder で青になるまでにやったことを紹介します。 AtCoder で黄色になる AtCoder黄色になりました。応援してくださった皆さんありがとうございました！！！！！！！ pic.twitter.com/6eYHW4P54Y— りきぽん (@ricky_quikem) 2021年3月27日 ARC に出る ARC …

E or m よりは、三 or 川 という感じがする 問題へのリンク 問題 各マスが白、黒、灰色に塗られた $ N \times M $ のグリッドが与えられる。 各灰マスを白か黒に塗り替えてできるグリッドのうち、以下のようにして生成できるものはいくつあるか？ グリッドの…

グリッドマンユニバースを見に行かないといけない 問題へのリンク 問題 白黒で塗られた $ N \times M $ のグリッドがある。 黒マス全体を連結にするために、追加で黒に塗るべきマスは最小でいくつ？ 制約 $ 1 \leq N \leq 100 $ $ 1 \leq M \leq 7 $ ← 小さ…

最後の一手で詰まっていた……。 問題へのリンク 問題 整数 $N$ が与えられる。 要素の総和が $N$ 隣り合う項の値が異なる を満たすような数列の長さの総和を $998244353$ で割った余りを求めよ。 前提 とくになし 解法 問題の第一印象は 「$N-1$ 個の条件を全…

H は Hadamard transform の H 問題へのリンク 問題 整数 $ N $ と、整数 $ A_1, A_2, \dots, A_K $ が与えられる。 $ 1 \leq M \leq N $ かつ $ d_i \in \Brace{A_1, A_2, \dots, A_K} $ を満たす長さ $ M $ の整数列 $ d $ のうち、 $$ d_1 \oplus d_2 \op…

放置している ABC - G, Ex を解き進めたい 問題へのリンク 問題 素数 $P$ が与えられる。 $ 0 \leq x \leq P - 1 $ $ 0 \leq y \leq P - 1 $ ある整数 $ n $ が存在して、$ x ^ n \equiv _ P y$ を満たす整数の組 $ (x, y) $ の個数を $ 998244353 $ で割っ…

考察をショートカットしたいので書きました。負の数が絡むと頭が壊れがち。 見つけ次第追加していこうと思います。 定義 床関数 $ x $ が有理数のとき 天井関数 $ x $ が有理数のとき 不等式評価 床関数 天井関数 切り捨て除算を使った実装 オーバーフローを…