我们称一个 n 阶排列 p 的超过数是满足 1≤i≤n 且 pi>i 的 i 的数量,降低数是满足 1≤i≤n−1 且 pi>pi+1 的 i 的数量。
记 n 阶排列中超过数为 m,同时降低数为 k 的排列数量为 h(n,m,k),请你对给定的 n 计算所有 h(n,m,k)。由于答案很大,你只需要输出它们对 M 取模的值即可。
输入格式
一行输入两个正整数 n 和 M,表示排列的阶数和模数。
输出格式
输出 n 行每行 n 个数,第 i 行第 j 个数输出 h(n,i−1,j−1)mod。
样例数据
样例 1 输入
3 998244353
样例 1 输出
1 0 0 0 3 1 0 1 0
样例 1 解释
- 超过数为 0,降低数为 0 的排列:[1, 2, 3]。
- 超过数为 1,降低数为 1 的排列:[2, 1, 3]、[3, 1, 2]、[1, 3, 2]。
- 超过数为 1,降低数为 2 的排列:[3, 2, 1]。
- 超过数为 2,降低数为 1 的排列:[2, 3, 1]。
样例 2 输入
7 998244353
样例 2 输出
1 0 0 0 0 0 0 0 21 70 28 1 0 0 0 35 343 596 209 8 0 0 35 470 1154 673 83 1 0 21 259 582 300 29 0 0 7 49 56 8 0 0 0 1 0 0 0 0 0
子任务
本题使用捆绑测试。
对于 10\% 的数据,保证 n \leq 10。
对于 30\% 的数据,保证 n \leq 20。
对于 60\% 的数据,保证 n \leq 35。
对于 100\% 的数据,保证 1 \le n \leq 60,M 是质数,10^8 \leq M \leq 10^9。
提示
你可以选择使用如下模板来加速取模运算。
#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
using LL = __uint128_t;
struct FastMod {
u64 b, m;
FastMod(u64 b) : b(b), m(u64((LL(1) << 64) / b)) {}
u64 operator()(u64 a) {
u64 q = (u64) ((LL(m) * a) >> 64);
u64 r = a - q * b;
return r >= b ? r - b : r;
}
} R(2);
int mod;
int main() {
int n; cin >> n >> mod; R = FastMod(mod);
int a = 1e7, b = 2e7;
int c = R(a * (u64)b);
return 0;
}