問題概略 A~Bの中で4か9が含まれる物の個数を答えよ。制約 A,B 解法 4か9が一つでも含まれてればいいなら包除原理使うか！と思ったけど、大変そうなので桁DPで解いた。 まとめ上げるのに必要な条件は 何桁目を見ているか 数が上限ギリギリかどうか すでに4,9…

問題概略 H*Wのマス目がある。好きなマスから好きなだけ自分より大きいマスへ隣に動ける。 移動経路の個数の余りを求めよ。制約 HW 解法 自分より大きいところへしか進めないため、閉路はない。 よって経路の数をマスごとにメモできる。 dpに-1を入れておき…