問題一覧 > 通常問題

No.821 Making Integers

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

問題文

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

操作：1≤i≤N を満たす整数 i を選択し、Ai の値を −1 倍する

入力

N K

1≤K≤N≤109

出力

操作後の数列 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もしくは右上の雲マークをクリックしてアカウントを作成してください。