#PQJ1415x7759. QOJ 1415_7759

    ID: 2599 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2023-2024 集训队互测动态规划

QOJ 1415_7759

标题: 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%): 无特殊限制。