「2025 ICPC 网络赛 2」I. DAG Query

发表于 分类于 本文字数： 2.3k 阅读时长 ≈ 2 分钟

Description

Link：QOJ 14322

This is an interactive problem.

给出一个 nn 个点 mm 条边的有向无环图（DAG）。你会得到该 DAG 的结构，但不会知道 DAG 中每条边的边权。

在任意一对顶点 ss 与 tt 之间可能存在多条路径，我们将一条路径的权值定义为该路径上所有边权的乘积。记 f(s,t,c)f(s, t, c) 表示从 ss 到 tt 的所有不同路径，在所有边权都乘以 cc 情况下的权值之和，对 998244353998244353 取模。

你可以进行至多 999999 次询问，每次询问你需要给出参数 s,t,cs, t, c，交互器会返回 f(s,t,c)f(s, t, c) 的值。

最后，交互器会给出一个参数 kk，你需要确定 f(1,n,k)f(1, n, k) 的值。

数据范围：1≤n≤1031 \leq n \leq 10^3，1≤m≤5×1031 \leq m \leq 5 \times 10^3。

时空限制：33s / 10241024MiB。

没啥意思的一道题，记录一下是为了扫清拉格朗日插值中的一些误区。

Solution

设 aia_i 表示从 11 到 nn 的所有长度为 ii 的路径的权值之和。此时会发现

f(1,n,x)=∑i=0n−1aixif(1, n, x) = \sum\limits_{i = 0}^{n - 1}a_ix^i

容易看出 f(1,n,x)f(1, n, x) 是一个关于 xx 的 n−1n - 1 次多项式，需要 nn 个点值才能拉插。

使用 n−1n - 1 次询问，得到 x=1…n−1x = 1 \dots n - 1 时 f(1,n,x)f(1, n, x) 的值。再加上 f(1,n,0)=0f(1, n, 0) = 0 这一个点值，刚好凑齐 nn 个点值，直接拉插！

误区 1：f(1,n,x)f(1, n, x) 可能并不是 n−1n - 1 次多项式，显然 11 到 nn 并不一定存在长度为 n−1n - 1 的路径，此时 an−1=0a_{n - 1} = 0 怎么办？

解释 1

确实！！！实际上给定 nn 个横坐标两两不同的点值，拉格朗日插值得出的多项式是至多 n−1n - 1 次，而不是恰好 n−1n - 1 次。

当数据恰好落在更低次的多项式上时，实际次数会更小。例如：(1,1),(2,4),(3,9),(4,16)(1, 1), (2, 4), (3, 9), (4, 16)，拉格朗日插值得出的多项式为 x2x^2。

但我们可以证明拉格朗日插值 f(x)=∑i=1nyi∏j≠ix−xjxi−xjf(x) = \sum_{i = 1}^{n} y_i \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}，是唯一的插值多项式。

证明 1：假设 g(x)g(x) 也是次数至多 n−1n - 1 次，且满足 g(xi)=yig(x_i) = y_i 的多项式。显然 f(x)−g(x)f(x) - g(x) 至少有 nn 个不相同的零点，但一个次数至多为 n−1n - 1 的非常数多项式的零点个数不可能超过 n−1n - 1 个，故 f(x)−g(x)f(x) - g(x) 恒等于 00。

证明 2：将 f(xi)=yif(x_i) = y_i 写成线性方程组

(1x1x12…x1n−11x2x22…x2n−1⋮⋮⋮⋱⋮1xnxn2…xnn−1)(a0a1⋮an−1)=(y1y2⋮yn)\begin{pmatrix} 1 & x_1 & x_1^2 & \dots & x_1^{n - 1} \\ 1 & x_2 & x_2^2 & \dots & x_2^{n - 1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n - 1} \\ \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ \vdots \\ a_{n - 1} \end{pmatrix} = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_{n} \end{pmatrix}

注意到系数矩阵是一个范德蒙德矩阵 MM，其行列式为

det⁡M=∏1≤i<j≤n(xj−xi)\det M = \prod_{1 \leq i < j \leq n} (x_j - x_i)

由于 xix_i 两两不同，故 det⁡M≠0\det M \neq 0，因此该方程组有唯一解。

误区 2：f(1,n,0)=0f(1, n, 0) = 0 不是非常显然的事情吗？这个点值真的有效吗？

解释 2

当然有效！是你多虑了。只要保证 nn 个点值的横坐标两两不同即可。

时间复杂度 O(n2)\mathcal{O}(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>

using s64 = long long;

template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}

template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

const int mod = 998244353;

void mul(int &x, int y) {
    x = 1ll * x * y % mod;
}

int qpow(int a, int b, int p) {
    int ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) ans = 1ll * ans * a % p;
        a = 1ll * a * a % p;
    }
    return ans;
}

const int N = 1010;

int n, m;

int ask(int x, int y, int c) {
    std::cout << "? " << x << ' ' << y << ' ' << c << std::endl;

    int res;
    std::cin >> res;

    return res;
}

int lagrange(std::vector< std::pair<int, int> > seq, int k) {
    int n = seq.size();
    int ans = 0;
    for (int i = 0; i < n; i ++) {
        int p = 1, q = 1;
        for (int j = 0; j < n; j ++) {
            if (i == j) continue;
            mul(p, k - seq[j].first);
            mul(q, seq[i].first - seq[j].first);
        }
        ans = (ans + 1ll * p * qpow(q, mod - 2, mod) % mod * seq[i].second) % mod;
    }
    return (ans + mod) % mod;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n >> m;

    for (int i = 1; i <= m; i ++) {
        int x, y;
        std::cin >> x >> y;
    }

    std::vector< std::pair<int, int> > seq(n);
    seq[0] = {0, 0};
    for (int i = 1; i < n; i ++) {
        seq[i] = {i, ask(1, n, i)};
    }

    std::cout << "!" << std::endl;

    int c;
    std::cin >> c;

    std::cout << lagrange(seq, c) << std::endl;

    return 0;
}