#P17217. [2025年南开中学集训]环

    ID: 16376 传统题 4000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-计数 DP滚动数组普通生成函数Lagrange 反演导数积分转化Lagrange 插值多项式除法模逆元

[2025年南开中学集训]环

环(circle)

题目描述

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

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

他需要连接 nn 条线,每个点恰好被一条线连接。

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

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

输入格式

第一行两个整数 nn 和 modmod,表示需要连接的线数和模数。

输出格式

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

样例 1 输入

3 998244353

样例 1 输出

0 0 3 1

样例 1 解释

对于该样例有:

这四种合法情况,交点数量分别为 2,2,2,32,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≤n≤1001\le n\le 100,108<mod≤109+710^8<mod\le 10^9+7 且 modmod 是质数。

子任务 分值 附加限制
1 10 n≤5n\le 5
2 20 n≤20n\le 20
3 n≤50n\le 50 且 mod=998244353mod=998244353
4 40 n≤50n\le 50
5 10 无特殊限制

提示与说明

使用 C++ 的选手可以使用下发文件中 KACTL 中的这一代码。这一名为 Barrett 模乘的算法可以以比通常计算快上数倍的速度计算 a mod ba\bmod b,其中 b>1b>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
}