#1785. Permutation Counting 2

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

Permutation Counting 2

Permutation Counting 2

题目描述

标题: Permutation Counting 2 - Problem - QOJ.ac

#7759. Permutation Counting 2

Statistics

The problem was used in the following contests:

给定 n,对于每组 x,y∈[0,n) 求出有多少个 1∼n 的排列 p 满足以下条件:

  • ∑i=1n−1[pi<pi+1]=x。
  • ∑i=1n−1[pi−1<pi+1−1]=y。

其中 p−1 表示 p 的逆排列,满足 ppi−1=i。

答案对给定的质数 MOD 取模。

输入格式

共一行,两个整数,表示 n,MOD。

输出格式

共 n 行,每行共 n 个整数,第 i 行第 j 列的数表示 x=i−1,y=j−1 时的答案。

样例

样例输入 1
3 1000000007
样例输出 1
1 0 0
0 4 0
0 0 1
样例输入 2
5 1000000007
样例输出 2
1 0 0 0 0
0 20 6 0 0
0 6 54 6 0
0 0 6 20 0
0 0 0 0 1
样例输入 3
10 1000000007
样例输出 3
1 0 0 0 0 0 0 0 0 0
0 165 462 330 55 1 0 0 0 0
0 462 9273 22023 13750 2266 66 0 0 0
0 330 22023 147301 203610 75306 6556 66 0 0 
0 55 13750 203610 592130 423236 75306 2266 1 0
0 1 2266 75306 423236 592130 203610 13750 55 0
0 0 66 6556 75306 203610 147301 22023 330 0
0 0 0 66 2266 13750 22023 9273 462 0
0 0 0 0 1 55 330 462 165 0
0 0 0 0 0 0 0 0 0 1

数据范围

对于 100% 数据,1≤n≤500,109≤MOD≤1.01×109,保证 MOD 为质数。

Subtask⁡1(10%):n≤8。

Subtask⁡2(15%):n≤16。

Subtask⁡3(25%):n≤40。

Subtask⁡4(25%):n≤100。

Subtask⁡5(25%): 无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 1000000007
1 0 0
0 4 0
0 0 1

样例 2

5 1000000007
1 0 0 0 0
0 20 6 0 0
0 6 54 6 0
0 0 6 20 0
0 0 0 0 1