环（circle）

题目描述

小 A 在复习计算几何，他手上有一个圆，圆上有 $2n$ 个点，依次编号为 $1\sim 2n$，这些点都在一般位置上。

一般位置指的是，任意三对点的连线不会相交于同一点。

他需要连接 $n$ 条线，每个点恰好被一条线连接。

他想要你帮他计算，对每个 $i$，这些线的交点数量恰好为 $i$，并且这些线连通的方案数。

由于答案可能很大，你需要对一个固定模数 $mod$ 取模。

输入格式

第一行两个整数 $n$ 和 $mod$，表示需要连接的线数和模数。

输出格式

一行 $\frac{n(n-1)}{2}+1$ 个数，第 $i$ 个数表示交点数量为 $i-1$ 的答案是多少。

样例 1 输入

3 998244353

样例 1 输出

0 0 3 1

样例 1 解释

对于该样例有：

这四种合法情况，交点数量分别为 $2,2,2,3$。

样例 2 输入

5 998244353

样例 2 输出

0 0 0 0 55 77 60 35 15 5 1

样例 3

见下发文件中的 circle/circle3.in 和 circle/circle3.ans。

数据范围

对于所有数据，保证 $1\le n\le 100$，$10^8<mod\le 10^9+7$ 且 $mod$ 是质数。

提示与说明

使用 C++ 的选手可以使用下发文件中 KACTL 中的这一代码。这一名为 Barrett 模乘的算法可以以比通常计算快上数倍的速度计算 $a\bmod b$，其中 $b>1$ 为一个编译时未知的常数。

#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
}