ゆらのふなびと

競プロ, Python, C++

重複組み合わせ

yukicoder No.389 ロジックパズルの組み合わせ

問題 M個のマスが1直線状に並んでいる。K個のヒントがあり、k番目のヒントは連続するH_k個のマスを塗れというものである。ただし異なるヒントによって塗られるマスどうしは隣接してはならない。このような塗り方は何通りあるか。mod 109 + 7 で答えよ。ただ…