D - Multiset Mean

Contest Duration: 2020-10-03(Sat) 12:00 - 2020-10-03(Sat) 14:00 (local time) (120 minutes) Back to Home

D - Multiset Mean Editorial

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : $700$ 点

問題文

正の整数 $N, K, M$ が与えられるので、 $1$ 以上 $N$ 以下の全ての整数 $x$ について、次の問題を解いてください。

$1, 2, 3 \cdots, N$ の各整数をそれぞれ $0$ 個以上 $K$ 個以下含むような空でない多重集合であって、平均が $x$ であるものの個数を $M$ で割った余りを求めよ。

制約

$1 \leq N, K \leq 100$
$10^8 \leq M \leq 10^9 + 9$
$M$ は素数である
入力は全て整数である

入力

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

 $N$   $K$   $M$

出力

以下の形式で出力せよ。

 $c_1$ 
 $c_2$ 
 $:$ 
 $c_N$

ただし $c_x$ は、平均が $x$ である多重集合の個数を $M$ で割った余りを表す。

入力例 1Copy

Copy

3 1 998244353

出力例 1Copy

Copy

1
3
1

$1$ 以上 $3$ 以下の整数をそれぞれ $0$ 個以上 $1$ 個以下含むような空でない多重集合を考えます。

平均が $x = 1$ である多重集合は、 $\{1\}$ の $1$ 個です。
平均が $x = 2$ である多重集合は、 $\{2\}, \{1, 3\}, \{1, 2, 3\}$ の $3$ 個です。
平均が $x = 3$ である多重集合は、 $\{3\}$ の $1$ 個です。

入力例 2Copy

Copy

1 2 1000000007

出力例 2Copy

Copy

$1$ 以上 $1$ 以下の整数をそれぞれ $0$ 個以上 $2$ 個以下含むような空でない多重集合を考えます。

平均が $x = 1$ である多重集合は、 $\{1\}, \{1, 1\}$ の $2$ 個です。

入力例 3Copy

Copy

10 8 861271909

出力例 3Copy

Copy

Score : $700$ points

Problem Statement

Given positive integers $N, K$ and $M$ , solve the following problem for every integer $x$ between $1$ and $N$ (inclusive):

Find the number, modulo $M$ , of non-empty multisets containing between $0$ and $K$ (inclusive) instances of each of the integers $1, 2, 3 \cdots, N$ such that the average of the elements is $x$ .

Constraints

$1 \leq N, K \leq 100$
$10^8 \leq M \leq 10^9 + 9$
$M$ is prime.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $K$   $M$

Output

Use the following format:

 $c_1$ 
 $c_2$ 
 $:$ 
 $c_N$

Here, $c_x$ should be the number, modulo $M$ , of multisets such that the average of the elements is $x$ .

Sample Input 1Copy

Copy

3 1 998244353

Sample Output 1Copy

Copy

1
3
1

Consider non-empty multisets containing between $0$ and $1$ instance(s) of each of the integers between $1$ and $3$ . Among them, there are:

one multiset such that the average of the elements is $k = 1$ : $\{1\}$ ;
three multisets such that the average of the elements is $k = 2$ : $\{2\}, \{1, 3\}, \{1, 2, 3\}$ ;
one multiset such that the average of the elements is $k = 3$ : $\{3\}$ .

Sample Input 2Copy

Copy

1 2 1000000007

Sample Output 2Copy

Copy

Consider non-empty multisets containing between $0$ and $2$ instances of each of the integers between $1$ and $1$ . Among them, there are:

two multisets such that the average of the elements is $k = 1$ : $\{1\}, \{1, 1\}$ .

Sample Input 3Copy

Copy

10 8 861271909

Sample Output 3Copy

Copy