atcoder.jp 二次元のある長方形領域 (r1≦y≦r2, c1≦x≦c2) の中の yCx の和を計算する問題。 とりあえず2次元の中の何かの和を考えるときは、包除原理を使うことにより 0≦y<≦r, 0≦x≦c で計算するルーチンを書いておき、あとから余計な部分を引くのが定石。 で…

atcoder.jp 桁DPの典型的な問題。非常にNの大きい問題で、N以下で条件を満たすものの数を数えよ、という場合はだいたい桁DPでやるのがよい。 DPは上位の桁(文字列でIndex 0の文字)から見て、状態として「ある桁まで見たとき、0以外の数がK個」「ある桁まで見…