問題一覧 > 通常問題

No.3030 Kruskal-Katona

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
0 ProblemId : 11892 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-11 15:10:02

問題文

任意の正整数 $N$ と $i$ について、一意的に整数 $N_i > N_{i-1} > \dots > N_j \geq j \geq 1$ が存在して、二項係数 $\displaystyle\binom{n}{m} = \frac{n!}{m!(n-m)!}$ を用いて

$\displaystyle N = \binom{N_i}{i} + \binom{N_{i-1}}{i-1} + \dots + \binom{N_j}{j}$

と表せることが知られています。入力から与えられる $N, i$ について、$N_i, N_{i-1}, \dots, N_j$ を求め、半角スペース一字で区切ってこの順番に出力してください。

入力

$N \ i$

$1 \leq N \leq 10^8,$
$1 \leq i \leq 100.$

出力

数字を半角スペース一字で区切って出力してください。最後に改行してください。

サンプル

サンプル1
入力
10 3
出力
5

$\displaystyle10 = \binom{5}{3}$ です。

サンプル2
入力
135 17
出力
18 17 16 15 14 13 12 11 10 9

$\displaystyle135=\binom{18}{17} + \binom{17}{16} + \binom{16}{15} + \binom{15}{14} + \binom{14}{13} + \binom{13}{12} + \binom{12}{11} + \binom{11}{10} + \binom{10}{9} + \binom{9}{8}$ です。

サンプル3
入力
1000 1
出力
1000

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