問題一覧 > 通常問題

No.821 Making Integers

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 217
作問者 : PulmnPulmn / テスター : ixmelixmel
2 ProblemId : 2901 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-04-26 21:14:16

問題文

正整数 $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 整数型に収まらない場合があります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。