#1785. Permutation Counting 2
Permutation Counting 2
Permutation Counting 2
题目描述
标题: Permutation Counting 2 - Problem - QOJ.ac
#7759. Permutation Counting 2
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 为质数。
Subtask1(10%):n≤8。
Subtask2(15%):n≤16。
Subtask3(25%):n≤40。
Subtask4(25%):n≤100。
Subtask5(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