/ 
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 で割った余りを表す。
入力例 1
3 1 998244353
出力例 1
1 3 1
1 以上 3 以下の整数をそれぞれ 0 個以上 1 個以下含むような空でない多重集合を考えます。
- 平均が x = 1 である多重集合は、\{1\} の 1 個です。
- 平均が x = 2 である多重集合は、\{2\}, \{1, 3\}, \{1, 2, 3\} の 3 個です。
- 平均が x = 3 である多重集合は、\{3\} の 1 個です。
入力例 2
1 2 1000000007
出力例 2
2
1 以上 1 以下の整数をそれぞれ 0 個以上 2 個以下含むような空でない多重集合を考えます。
- 平均が x = 1 である多重集合は、\{1\}, \{1, 1\} の 2 個です。
入力例 3
10 8 861271909
出力例 3
8 602 81827 4054238 41331779 41331779 4054238 81827 602 8
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 1
3 1 998244353
Sample Output 1
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 2
1 2 1000000007
Sample Output 2
2
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 3
10 8 861271909
Sample Output 3
8 602 81827 4054238 41331779 41331779 4054238 81827 602 8