問題一覧 > 通常問題

No.3030 Kruskal-Katona

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

問題文

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

N=(Nii)+(Ni−1i−1)+⋯+(Njj)\displaystyle N = \binom{N_i}{i} + \binom{N_{i-1}}{i-1} + \dots + \binom{N_j}{j}

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

入力

N iN \ i

1≤N≤108,1 \leq N \leq 10^8,
1≤i≤100.1 \leq i \leq 100.

出力

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

サンプル

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

10=(53)\displaystyle10 = \binom{5}{3} です。

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

135=(1817)+(1716)+(1615)+(1514)+(1413)+(1312)+(1211)+(1110)+(109)+(98)\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もしくは右上の雲マークをクリックしてアカウントを作成してください。