最大連長制約 Python2編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
自然数 A, B が与えられます。
0 と 1 のみで構成される長さ L の文字列で 0 が A+1 個以上、1 が B+1 個以上連続しないという条件を満たすものはいくつありますか。
ただし、答えは非常に大きくなる場合があるので 10^10 で割ったあまりを出力してください。
例えば L=4, A=2, B=3 (入力例 1 ) で条件を満たさない文字列は 0000, 0001, 1000, 1111 の 4 つです。
0 と 1 で構成された長さ 4 の文字列は 16 個あるため、この 4 つを除く 12 個が答えとなります。
また、 L=4, A=4, B=5 (入力例 2 ) で条件を満たさない文字列はありません。
したがって答えは 16 となります。
ヒント:
状態として「最後の文字が何かとその文字が何回連続しているか」を持ってください。
- 入力される値
-
L A B
・非負整数 L, A, B が １ 行で空白区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
条件を満たす文字列の個数を 1 行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて, 以下の条件をみたします
・入力はすべて整数
・1 ≦ L ≦ 2,000
・1 ≦ A, B ≦ 1,000
- 入力例1
-
4 2 3
- 出力例1
-
12
- 入力例2
-
4 4 5
- 出力例2
-
16
- 入力例3
-
30 5 10
- 出力例3
-
862882191
