No.821 Making Integers

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 135
作問者 : PulmnPulmn / テスター : ixmelixmel
0 ProblemId : 2901 / 出題時の順位表

問題文

正整数 $N,K$ が与えられます。長さ $N$ の数列 $A=(1,2,\dots ,N)$ に次の操作を $0$ 回以上 $K$ 回以下行ったとき、数列 $A$ の総和としてあり得る値の通り数を求めてください。

操作:$1\le i\le N$ を満たす整数 $i$ を選択し、$A_i$ の値を $-1$ 倍する

入力

$N$ $K$

$1\le K\le N\le 10^9$

出力

操作後の数列 $A$ の総和としてあり得る値の通り数を出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 2
出力
6

操作後の数列 $A$ としてあり得るのは $(1,2,3),(-1,2,3),(1,-2,3),(1,2,-3),(-1,-2,3),(-1,2,-3),(1,-2,-3)$ です。その総和はそれぞれ $6,4,2,0,0,-2,-4$ となるので、操作後の数列の総和としてあり得る値は $6$ 通りあります。

サンプル2
入力
987654321 123456789
出力
114311841799268404

答えは 32-bit 整数型に収まらない場合があります。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。