新年的神谕
神说：“简洁问题触及本质。”
神说：“复杂并非深刻，混乱亦非自由。”
神说：“剥离偶然，留下必然。”
神说：“$\exp(O(n))$ 是虚伪的胜利，$\text{poly}(n)$ 是永恒的真理。”
这是一位算法竞赛前选手接收到的最后一份神谕，在他与他的朋友的精心打磨下，最终呈现出了这份礼物赠予各位。
形式化题意：
给定 $n$，将所有满足 $S\subseteq [n],1\le |S|\le 2$ 的集合 $S$ 排成一列，要求 $\{x,y\}$ 在 $\{x\}$ 与 $\{y\}$ 之间，且 $\{x\}$ 在 $\{x+1\}$ 之前。
对于每一组 $1\le i\le n,1\le j\le n(n+1)/2$ 求出 $\{i\}$ 的下标为 $j$ 的方案数。答案对给定的质数 $p$ 取模。
输入格式
共一行，两个整数 $n,p$。
输出格式
共 $n$ 行，每行 $n(n+1)/2$ 个整数。第 $i$ 行的第 $j$ 个数，表示 $\{i\}$ 的下标为 $j$ 的方案数。
1 851214401
1
3 922820713
4 0 0 0 0 0
0 0 2 2 0 0
0 0 0 0 0 4
4 682679827
144 0 0 0 0 0 0 0 0 0
0 0 60 60 24 0 0 0 0 0
0 0 0 0 0 24 60 60 0 0
0 0 0 0 0 0 0 0 0 144
样例四 $\sim$ 样例十
见下发文件。
数据范围
对于 $100\%$ 的数据，$1\le n\le 40,10^8< p< 10^9$。保证 $p$ 为质数。
| 子任务编号 | $n\le$ | 分值 |
|---|---|---|
| $1$ | $5$ | $5$ |
| $2$ | $10$ | $5$ |
| $3$ | $15$ | $10$ |
| $4$ | $20$ | $10$ |
| $5$ | $25$ | $15$ |
| $6$ | $30$ | $15$ |
| $7$ | $35$ | $20$ |
| $8$ | $40$ | $20$ |
时间限制：$5\text{s}$
空间限制：$1\text{GB}$
我们提供 $\text{Barrett}$ 模乘算法模板以加速取模运算：
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {
ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
};
FastMod F(2);
int main() {
int M = 1000000007; F = FastMod(M);
ull x = 10ULL*M+3;
cout <<; x << " " << F.reduce(x) << "\n"; // 10000000073 3
}