#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int p = 998244353;
const int g = 3;
const int W = 65536;
ll fp(ll a, ll b) {
    ll s = 1;

    for (; b; b >>= 1, a = a * a % p)
        if (b & 1)
            s = s * a % p;

    return s;
}
const int I = fp(g, (p - 1) / 4);
int rev[150000];
int w[150000];
void ntt(int *a, int n, int t) {
    for (int i = 1; i < n; i++) {
        rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? n >> 1 : 0);

        if (rev[i] > i)
            swap(a[rev[i]], a[i]);
    }

    for (int i = 2; i <= n; i <<= 1)
        for (int j = 0; j < n; j += i)
            for (int k = 0; k < i / 2; k++) {
                int u = a[j + k];
                int v = (ll)a[j + k + i / 2] * w[W / i * k] % p;
                a[j + k] = (u + v) % p;
                a[j + k + i / 2] = (u - v) % p;
            }

    if (t == -1) {
        reverse(a + 1, a + n);
        int inv = fp(n, p - 2);

        for (int i = 0; i < n; i++)
            a[i] = (ll)a[i] * inv % p;
    }
}
void mul(int *a, int *b, int *c, int n, int m, int l = -1) {
    if (l == -1)
        l = n + m;

    static int a1[150000], a2[150000];
    int k = 1;

    while (k <= n + m)
        k <<= 1;

    for (int i = 0; i < k; i++)
        a1[i] = a2[i] = 0;

    for (int i = 0; i <= n; i++)
        a1[i] = a[i];

    for (int i = 0; i <= m; i++)
        a2[i] = b[i];

    ntt(a1, k, 1);
    ntt(a2, k, 1);

    for (int i = 0; i < k; i++)
        a1[i] = (ll)a1[i] * a2[i] % p;

    ntt(a1, k, -1);

    for (int i = 0; i <= l; i++)
        c[i] = a1[i];
}
void inv(int *a, int *b, int n) {
    if (n == 1) {
        b[0] = fp(a[0], p - 2);
        return;
    }

    inv(a, b, n >> 1);
    static int a1[150000], a2[150000];

    for (int i = 0; i < n; i++)
        a1[i] = a[i];

    for (int i = n; i < n << 1; i++)
        a1[i] = 0;

    for (int i = 0; i<n >> 1; i++)
        a2[i] = b[i];

    for (int i = n >> 1; i < n << 1; i++)
        a2[i] = 0;

    ntt(a1, n << 1, 1);
    ntt(a2, n << 1, 1);

    for (int i = 0; i < n << 1; i++)
        a1[i] = a2[i] * (2 - (ll)a1[i] * a2[i] % p) % p;

    ntt(a1, n << 1, -1);

    for (int i = 0; i < n; i++)
        b[i] = a1[i];
}
void getmod(int *a, int *b, int *c, int n, int m) {
    static int a1[150000], a2[150000], a3[150000];

    for (int i = 0; i <= n; i++)
        a1[i] = a[n - i];

    for (int i = 0; i <= m; i++)
        a2[i] = b[m - i];

    for (int i = m + 1; i <= n; i++)
        a2[i] = 0;

    int k = 1;

    while (k <= n - m)
        k <<= 1;

    for (int i = n + 1; i < k; i++)
        a1[i] = a2[i] = 0;

    inv(a2, a3, k);
    mul(a1, a3, a3, n - m, n - m, n - m);

    for (int i = 0; i <= n - m; i++)
        a2[i] = a3[n - m - i];

    mul(b, a2, a3, m, n - m, m);

    for (int i = 0; i < m; i++)
        c[i] = (a[i] - a3[i]) % p;
}
int n;
int x[200010];
int y[200010];
int a[200010];
int *s1[400010];
int *s2[400010];
int s[200010];
void gao(int now, int l, int r) {
    if (l == r) {
        s1[now] = new int[2];
        s1[now][1] = 1;
        s1[now][0] = -a[l];
        return;
    }

    int mid = (l + r) >> 1;
    int ls = now << 1;
    int rs = (now << 1) | 1;
    gao(ls, l, mid);
    gao(rs, mid + 1, r);
    s1[now] = new int[r - l + 2];
    mul(s1[ls], s1[rs], s1[now], mid - l + 1, r - mid);
}
void gao2(int now, int l, int r) {
    if (l == r) {
        s[l] = s2[now][0];
        return;
    }

    int mid = (l + r) >> 1;
    int ls = now << 1;
    int rs = (now << 1) | 1;
    s2[ls] = new int[mid - l + 1];
    s2[rs] = new int[r - mid];
    getmod(s2[now], s1[ls], s2[ls], r - l, mid - l + 1);

    if (r <= n / 2)
        getmod(s2[now], s1[rs], s2[rs], r - l, r - mid);

    gao2(ls, l, mid);

    if (r <= n / 2)
        gao2(rs, mid + 1, r);
}
pii b[100010];
int cmp(pii a, pii b) {
    return pii(a.second, a.first) > pii(b.second, b.first);
}
int main() {

    w[0] = 1;
    w[1] = fp(g, (p - 1) / W);

    for (int i = 2; i < W; i++)
        w[i] = (ll)w[i - 1] * w[1] % p;

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        scanf("%d%d", &b[i].first, &b[i].second);

    sort(b + 1, b + n + 1, cmp);

    for (int i = 1; i <= n; i++) {
        x[i] = b[i].first;
        y[i] = b[i].second;
        a[i] = (x[i] + (ll)y[i] * I) % p;
    }

    gao(1, 1, n);
    s2[1] = new int[n];

    for (int i = 1; i <= n; i++)
        s2[1][i - 1] = (ll)s1[1][i] * i % p;

    gao2(1, 1, n);
    ll ans = 0;

    for (int i = 1; i <= n; i++)
        if (y[i] > 0)
            ans = (ans + fp(s[i], p - 2)) % p;

    ans = ans * 2 * I % p;
    ans = (ans + p) % p;
    printf("%lld\n", ans);
    return 0;
}

古明地恋与小石子的曲线面积问题 题解

算法标签

复分析（留数定理）、多项式分治乘法（NTT加速）、分治多项式求值、多项式模运算、数论（模逆元/单位根）、快速傅里叶变换（NTT）

题目分析

核心问题转化

题目本质是通过几何操作推导曲线函数，再通过积分求面积，最终转化为多项式导数与根的数论计算问题。关键转化步骤如下：

1. 操作的复数表示

恋恋在x轴上的位置为 $(t, 0)$，石子 $P_i(x_i, y_i)$ 相对于恋恋的位置可表示为复数 $z_i = (x_i - t) + i y_i$。
旋转+缩放操作等价于复数乘法（旋转$\theta$角+缩放$r$倍 = 乘以 $r(\cos\theta + i\sin\theta)$）。所有操作的复合的是所有 $z_i$ 的乘积（复数乘法满足结合律）。

2. 目标向量的约束

要求所有操作后初始向量 $(1,0)$ 变为 $(1,0)$，即初始向量 $v$ 满足 $v \cdot \prod z_i = 1$，故 $v = 1/\prod z_i$。
将 $v$ 逆时针旋转90度（等价于乘以 $i$），末端形成的曲线函数为 $f(t) = \text{Im}(v \cdot i)$。结合题目特殊性质（操作后x轴向量仍在x轴），可推得 $\prod z_i$ 是实系数多项式 $F(t)$，因此 $f(t) = 1/F(t)$。

3. 面积与积分计算

曲线与x轴的面积为 $\int_{-\infty}^{+\infty} 1/F(t) dt$。根据留数定理，实系数多项式 $F(t)$ 的积分结果为 $\pi \cdot S$（$S$ 为有理数），题目要求输出 $S \mod 998244353$（即面积除以 $\pi$ 的结果）。

4. 留数定理简化

$F(t)$ 的根为复数 $\alpha_i = x_i + i y_i$（共轭成对出现），上半平面的根对应 $y_i > 0$。积分结果除以 $\pi$ 后为：

$$S = 2i \cdot \sum_{\substack{i=1 \\ y_i > 0}}^n \frac{1}{F'(\alpha_i)} $$

其中 $F'(\alpha_i)$ 是 $F(t)$ 在根 $\alpha_i$ 处的导数。

关键难点

• $n$ 可达 $6e4$，需高效计算多项式乘积（$F(t) = \prod (t - \alpha_i)$）和每个根的导数逆元（$1/F'(\alpha_i)$）。
• 复数运算需在模 $998244353$ 下实现（用4次单位根 $I$ 表示 $i$，满足 $I^2 \equiv -1 \mod 998244353$）。

核心思路

1. 复数模表示：用模 $998244353$ 的4次单位根 $I$ 表示虚数单位 $i$，每个石子的复数 $\alpha_i = x_i + y_i \cdot I \mod 998244353$。
2. 分治NTT构建多项式：通过分治将 $n$ 个一次多项式 $(t - \alpha_i)$ 相乘，得到 $F(t) = \prod_{i=1}^n (t - \alpha_i)$（monic多项式，首项系数为1），时间复杂度 $O(n \log^2 n)$。
3. 分治求导数逆元：对于每个根 $\alpha_i$，利用多项式导数性质 $F'(\alpha_i) = \prod_{j \neq i} (\alpha_i - \alpha_j)$，通过分治+多项式模运算高效计算 $1/F'(\alpha_i) \mod 998244353$。
4. 求和与修正：对 $y_i > 0$ 的根求和 $1/F'(\alpha_i)$，乘以 $2I \mod 998244353$，得到最终答案。

算法步骤

步骤1：预处理单位根与NTT参数

• 4次单位根 $I$：$I = g^{(p-1)/4} \mod p$（$g$ 是 $p=998244353$ 的原根），满足 $I^2 \equiv -1 \mod p$。
• NTT预处理：预计算旋转因子 $w$，用于多项式乘法加速。

步骤2：石子复数表示与排序

• 对每个石子 $(x_i, y_i)$，计算 $\alpha_i = (x_i + y_i \cdot I) \mod p$。
• 排序石子（按 $y_i$ 降序，不影响多项式乘积结果，仅为分治计算方便）。

步骤3：分治NTT构建多项式 $F(t)$

• 分治函数 gao(now, l, r)：递归将区间 $[l, r]$ 内的一次多项式 $(t - \alpha_i)$ 相乘，结果存储在 s1[now] 中。
• 合并区间时，用NTT加速多项式乘法（时间复杂度 $O(k \log k)$，$k$ 为多项式次数）。

步骤4：分治计算 $1/F'(\alpha_i)$

• 导数 $F'(t)$ 的系数：$F(t) = \sum_{k=0}^n c_k t^k$，则 $F'(t) = \sum_{k=1}^n k \cdot c_k t^{k-1}$，故 s2[1][i-1] = c_i * i mod p。
• 分治函数 gao2(now, l, r)：通过多项式模运算（getmod），将大区间多项式对小区间多项式取模，递归计算每个 $\alpha_i$ 对应的 $1/F'(\alpha_i)$，存储在 s[i] 中。

步骤5：计算最终答案

• 求和：对所有 $y_i > 0$ 的石子，累加 $s[i]$（即 $1/F'(\alpha_i)$）。
• 修正：求和结果乘以 $2 \cdot I \mod p$，确保结果非负后输出。

代码解析

核心工具函数

1. 快速幂与单位根

ll fp(ll a, ll b) { /* 快速幂求 a^b mod p */ }
const int I = fp(g, (p - 1) / 4); // 4次单位根，I^2 ≡ -1 mod p

• $I$ 是虚数单位 $i$ 的模 $p$ 表示，用于复数运算。

2. NTT与多项式乘法

void ntt(int *a, int n, int t) { /* NTT变换（t=1正向，t=-1逆向） */ }
void mul(int *a, int *b, int *c, int n, int m) { /* NTT加速多项式乘法 */ }

• 多项式乘法时间复杂度 $O(k \log k)$，$k$ 为结果多项式的次数上限（2的幂次）。

3. 多项式求逆与模运算

void inv(int *a, int *b, int n) { /* 多项式求逆（NTT加速） */ }
void getmod(int *a, int *b, int *c, int n, int m) { /* 多项式除法求余 */ }

• 多项式求逆用于分治中计算子区间多项式的逆，支持快速模运算。

4. 分治构建多项式

void gao(int now, int l, int r) {
    if (l == r) {
        s1[now] = new int[2];
        s1[now][1] = 1; s1[now][0] = -a[l]; // 一次多项式 t - a[l]
        return;
    }
    int mid = (l + r) >> 1;
    gao(now<<1, l, mid); gao(now<<1|1, mid+1, r);
    mul(s1[now<<1], s1[now<<1|1], s1[now], mid-l+1, r-mid); // 合并子区间多项式
}

• 递归构建区间 $[l..r]$ 的多项式乘积，叶子节点为一次多项式 $(t - a[l])$。

5. 分治求导数逆元

void gao2(int now, int l, int r) {
    if (l == r) { s[l] = s2[now][0]; return; } // 叶子节点直接取结果
    int mid = (l + r) >> 1;
    getmod(s2[now], s1[now<<1], s2[now<<1], r-l, mid-l+1); // 模左子区间多项式
    if (r <= n/2) getmod(s2[now], s1[now<<1|1], s2[now<<1|1], r-l, r-mid); // 模右子区间多项式
    gao2(now<<1, l, mid);
    if (r <= n/2) gao2(now<<1|1, mid+1, r);
}

• 通过多项式除法求余，将每个根对应的导数逆元递归计算，避免 $O(n^2)$ 复杂度。

主函数逻辑

int main() {
    // 1. 预处理NTT旋转因子
    w[0] = 1; w[1] = fp(g, (p-1)/W);
    for (int i=2; i<W; i++) w[i] = (ll)w[i-1] * w[1] % p;
    
    // 2. 读入数据并转换为复数表示
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d%d", &b[i].first, &b[i].second);
    sort(b+1, b+n+1, cmp); // 按y降序排序
    for (int i=1; i<=n; i++) {
        x[i] = b[i].first; y[i] = b[i].second;
        a[i] = (x[i] + (ll)y[i] * I) % p; // 复数α_i = x_i + y_i*I
    }
    
    // 3. 分治构建多项式F(t) = product(t - a[i])
    gao(1, 1, n);
    
    // 4. 预处理导数系数 s2[1][i-1] = c_i * i（c_i是F(t)的系数）
    s2[1] = new int[n];
    for (int i=1; i<=n; i++) s2[1][i-1] = (ll)s1[1][i] * i % p;
    
    // 5. 分治计算1/F'(a[i])
    gao2(1, 1, n);
    
    // 6. 求和并修正得到答案
    ll ans = 0;
    for (int i=1; i<=n; i++) if (y[i] > 0) ans = (ans + fp(s[i], p-2)) % p;
    ans = ans * 2 * I % p; // 乘以2I
    ans = (ans + p) % p; // 确保非负
    printf("%lld\n", ans);
}

复杂度分析

步骤	时间复杂度	说明
NTT预处理	$O(W)$	$W=65536$（常数级）
分治构建多项式	$O(n \log^2 n)$	每层分治的多项式乘法总复杂度 $O(n \log n)$，共 $\log n$ 层
分治求导数逆元		与多项式构建复杂度一致
求和与修正	$O(n)$	线性遍历石子

总时间复杂度：$O(n \log^2 n)$，适配 $n=6e4$（$6e4 \times (20)^2 = 2.4e7$ 运算量，可控）。
空间复杂度：$O(n \log n)$，用于存储分治过程中的多项式和临时数组。

关键注意事项

1. 复数模表示的正确性：$I$ 必须是4次单位根，确保 $I^2 \equiv -1 \mod p$，否则复数运算失效。
2. 多项式乘法的模运算：所有多项式操作需在模 $998244353$ 下进行，避免溢出和结果错误。
3. 导数逆元的计算：通过分治+多项式模运算，避免直接计算 $O(n^2)$ 的乘积，确保效率。
4. 符号修正：最终结果需乘以 $2I$ 并调整为非负，符合题目对模运算的要求。

样例验证

样例输入 $n=2$，石子 $(1,2)$ 和 $(1,-2)$：

1. 复数表示：$\alpha_1=1+2I$，$\alpha_2=1-2I$。
2. 多项式 $F(t)=(t-\alpha_1)(t-\alpha_2)=t^2-2t+5$。
3. 导数 $F'(t)=2t-2$，$F'(\alpha_1)=4I$，$1/F'(\alpha_1)=-I/4$。
4. 求和（仅 $y_1>0$）：$-I/4$，乘以 $2I$ 得 $2I \times (-I/4) = 1/2$。
5. $1/2 \mod 998244353 = 499122177$，与样例输出一致。