G - Coefficient Stair Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

非負整数からなる長さ N の列 A=(A _ 1,A _ 2,\ldots,A _ N) であって、\displaystyle\sum _ {i=1} ^ Ni\times A _ i=K を満たすものを辞書順で小さいほうからすべて出力してください。

ここで、条件を満たす数列が 3\times10 ^ 5 個以下であるような入力のみが与えられます。

数列の辞書順とは？

数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは，下記の 1. と 2. のどちらかが成り立つことを言います． ここで，|S|, |T| はそれぞれ S, T の長さを表します．

  1. |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})．
  2. ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して，下記の 2 つがともに成り立つ．
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
    • S_i が T_i より（数として）小さい．

制約

  • 1\le N\le 10
  • 1\le K\le 2\times10 ^ 5
  • 条件を満たす数列は 3\times10 ^ 5 個以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

条件を満たす非負整数列が q 個あるとして、q 行にわたって出力せよ。 それぞれの行には条件を満たす非負整数列の要素を空白を区切りとして順に出力せよ。 どの数列についても、その数列より前に出力された数列はどれもその数列より辞書順で小さくなければならない。

入力例 1

3 8

出力例 1

0 1 2
0 4 0
1 2 1
2 0 2
2 3 0
3 1 1
4 2 0
5 0 1
6 1 0
8 0 0

例えば、列 (0,1,2) は 0\times1+1\times2+2\times3=0+2+6=8 となるため条件を満たします。 条件を満たす列であってこれより辞書順で小さいものは存在しないため、1 行目には 0 1 2 を出力してください。

(0,1,2) とあわせて 10 個の列が条件を満たします。 これらを辞書順で小さいほうから出力してください。

入力例 2

1 200000

出力例 2

200000

入力例 3

8 9

出力例 3

0 0 0 1 1 0 0 0
0 0 1 0 0 1 0 0
0 0 3 0 0 0 0 0
0 1 0 0 0 0 1 0
0 1 1 1 0 0 0 0
0 2 0 0 1 0 0 0
0 3 1 0 0 0 0 0
1 0 0 0 0 0 0 1
1 0 0 2 0 0 0 0
1 0 1 0 1 0 0 0
1 1 0 0 0 1 0 0
1 1 2 0 0 0 0 0
1 2 0 1 0 0 0 0
1 4 0 0 0 0 0 0
2 0 0 0 0 0 1 0
2 0 1 1 0 0 0 0
2 1 0 0 1 0 0 0
2 2 1 0 0 0 0 0
3 0 0 0 0 1 0 0
3 0 2 0 0 0 0 0
3 1 0 1 0 0 0 0
3 3 0 0 0 0 0 0
4 0 0 0 1 0 0 0
4 1 1 0 0 0 0 0
5 0 0 1 0 0 0 0
5 2 0 0 0 0 0 0
6 0 1 0 0 0 0 0
7 1 0 0 0 0 0 0
9 0 0 0 0 0 0 0

Score : 400 points

Problem Statement

Output all length-N sequences A=(A _ 1,A _ 2,\ldots,A _ N) consisting of non-negative integers that satisfy \displaystyle\sum _ {i=1} ^ Ni\times A _ i=K, in lexicographic order from smallest to largest.

Here, you will only receive inputs such that the number of sequences satisfying the condition is at most 3\times10 ^ 5.

What is lexicographic order for sequences?

A sequence S = (S_1,S_2,\ldots,S_{|S|}) is said to be lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) if either 1. or 2. below holds. Here, |S| and |T| denote the lengths of S and T, respectively.

  1. |S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. There exists an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold.
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
    • S_i is (numerically) smaller than T_i.

Constraints

  • 1\le N\le 10
  • 1\le K\le 2\times10 ^ 5
  • The number of sequences satisfying the condition is at most 3\times10 ^ 5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K

Output

Let q be the number of sequences of non-negative integers satisfying the condition; output them over q lines. Each line should contain the elements of a sequence of non-negative integers satisfying the condition, in order, separated by spaces. For every sequence, all sequences outputed before it must be lexicographically smaller than it.

Sample Input 1

3 8

Sample Output 1

0 1 2
0 4 0
1 2 1
2 0 2
2 3 0
3 1 1
4 2 0
5 0 1
6 1 0
8 0 0

For example, for the sequence (0,1,2) we have 0\times1+1\times2+2\times3=0+2+6=8, so it satisfies the condition. There is no sequence satisfying the condition that is lexicographically smaller than this one, so output 0 1 2 on the first line.

Including (0,1,2), ten sequences satisfy the condition. Output these in lexicographic order from smallest to largest.

Sample Input 2

1 200000

Sample Output 2

200000

Sample Input 3

8 9

Sample Output 3

0 0 0 1 1 0 0 0
0 0 1 0 0 1 0 0
0 0 3 0 0 0 0 0
0 1 0 0 0 0 1 0
0 1 1 1 0 0 0 0
0 2 0 0 1 0 0 0
0 3 1 0 0 0 0 0
1 0 0 0 0 0 0 1
1 0 0 2 0 0 0 0
1 0 1 0 1 0 0 0
1 1 0 0 0 1 0 0
1 1 2 0 0 0 0 0
1 2 0 1 0 0 0 0
1 4 0 0 0 0 0 0
2 0 0 0 0 0 1 0
2 0 1 1 0 0 0 0
2 1 0 0 1 0 0 0
2 2 1 0 0 0 0 0
3 0 0 0 0 1 0 0
3 0 2 0 0 0 0 0
3 1 0 1 0 0 0 0
3 3 0 0 0 0 0 0
4 0 0 0 1 0 0 0
4 1 1 0 0 0 0 0
5 0 0 1 0 0 0 0
5 2 0 0 0 0 0 0
6 0 1 0 0 0 0 0
7 1 0 0 0 0 0 0
9 0 0 0 0 0 0 0