No.834 Random Walk Trip
タグ : / 解いたユーザー数 51
作問者 :


問題文
世界には
国
ただ旅行するだけではつまらないと感じたA君は、旅の過程をコインで決めることにしました。
旅行の日程は
(1) コインを投げて表と裏のどちらが出たかを観測します。
(2) 表が出た場合、
裏が出た場合、
(3) 上記(2)の後にA君がいる国を国
数列
ただし、答えは非常に大きくなることがあるので、答えを
入力
入力は以下の制約を満たします。
出力
条件を満たす数列の個数を
サンプル
サンプル1
入力
2 3
出力
4
投げたコインの表裏が、1日目から順に(裏、裏、表)だったとすると、
1日目に国1から国2に移動し、2日目には国2にとどまり、3日目には国2から国1に帰るので、数列
同様に、
(裏、表、表)のとき数列
(表、表、表)のとき数列
(表、裏、表)のとき数列
となり、問題の条件を満たす数列はこれですべてです。
よって、答えは
サンプル2
入力
1 2
出力
1
数列
サンプル3
入力
16 21
出力
352716
サンプル4
入力
1000000 1000000
出力
996692777
答えを
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。