#1932. Yet Another Permutation Problem

    ID: 1932 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest2294来源:qoj.ac数据:公开样例组合数学数学

Yet Another Permutation Problem

Yet Another Permutation Problem

题目描述

标题: Yet Another Permutation Problem - Problem - QOJ.ac

#13456. Yet Another Permutation Problem

Statistics

给定一个长度为 n 的排列 [1,2,…,n],你可以进行以下操作:

  • 选择一个数,将其取出然后放到排列的开头或末尾。

对每个 k=0,1,…,n−1,求出进行至多 k 次操作可能得到的排列个数。由于这些数可能非常大,你只需要回答它们除以 m 的余数即可。

输入格式

一行两个整数 n,m(1≤n≤1000,108≤m≤109+9,m 是素数)。

输出格式

n 行,第 i 行一个整数表示 k=i−1 时的答案。

样例数据

样例 1 输入

3 998244353

样例 1 输出

1
5
6

样例 1 解释

n=3 时,进行至多 1 次操作可以得到除 [3,2,1] 外的所有排列。

样例 2 输入

1 100000007

样例 2 输出

1

样例 3 输入

20 1000000009

样例 3 输出

1
39
1100
26220
554040
10581480
184187520
930255982
586386822
781249333
374807160
139825602
462558935
67876942
578348054
201415654
108018732
350356788
280522125
280522126

样例 3 解释

注意答案需要对 m 取模。

子任务

Subtask #1 (10 points): n≤10。

Subtask #2 (10 points): n≤18。

Subtask #3 (10 points): n≤50。

Subtask #4 (30 points): n≤300。

Subtask #5 (40 points): 无额外限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 998244353
1
5
6

样例 2

1 100000007
1