Newton 恒等式

· · 算法·理论

设现有 n 个数 a_1 \sim a_n,定义 a 的幂和

p_k=\sum_{i=1}^n a_i^k

取初等对称多项式

e_k=\sum _{1 \le i_1<i_2<\cdots<i_k \le n} \prod_{j=1}^k a_{i_j}

通俗来说,e_k 表示从 a_1 \sim a_n 中取 k 个数相乘的总和。约定 e_0=1,以及 e_m=0(m>n)。

Newton 恒等式指出

\boxed{ke_k=\sum_{i=1}^k (-1)^{i-1} e_{k-i} p_i}

下面给出组合意义证明。

将右侧式子化为

\begin{aligned} &\sum_{i=1}^k (-1)^{i-1} e_{k-i} p_i \\ =& \sum_{i=1}^k (-1)^{i-1} \sum_{S \subseteq U, |S|=k-i} \sum_{j=1}^n \left(\prod_{t \in S} a_t\right) a_j^i \end{aligned}

其中 U=\{1,2,\cdots,n\}。记 x_S=\prod \limits_{i \in S} a_i,取三元组 (i,S,j),权值为 (-1)^{i-1} x_S a_j^i,只要证所有权值求和等于 ke_k。

我们构造若干配对,将贡献尽可能抵消。

当且仅当 i=1 \land j \notin S 时权值保留。设 T=S \cup\{j\},权值 x_T=a_j x_S 且 |T|=k。

任取 j \in T 的选法数为 k,总贡献

k\sum_{|T|=k}\prod_{i \in T} a_i=ke_k

得证。

一个 trivial 的应用是,维护 e_k 可以转而维护幂和。下面给出 k 较小的若干特例:

一般地,已知 p_1\sim p_k 即可递推出 e_1 \sim e_k,复杂度 O(k^2)。

使用分治 NTT 可做到 O(k \log^2 k),利用 GF 配合多项式 \exp 做到 O(k \log k)。这些科技不在本文讨论范围内,故略去。

下面给出一个神奇的应用,做法来自 xueshengyi 大神。

维护 n 个集合 S_1\sim S_n,支持 q 次操作:

  • 给定 l,r,x,对 i \in [l,r] 令 S_i \gets S_i \cup \{x\}。保证操作前 x 不被包含。

  • 给定 l,r,x,对 i \in [l,r] 令 S_i \gets S_i \setminus\{x\}。保证操作前 x 被包含。

  • 给定 u,v,判定 S_u 与 S_v 的包含关系,保证 \textcolor{red}{\left||S_u|-|S_v|\right| \le k}。

    具体地,你需要判断 S_u =S_v 或 S_u \subsetneq S_v 或 S_v \subsetneq S_u 或其他。

取大质数 p=2^{61}-1 在 \mathbb{Z}_p 中运算。对集合 S,取幂和 H_i(S)=\sum \limits_{x \in S} h^i(x) 作为其 Hash 值。元素哈希 h 是 U\to \mathbb{Z}_{p} 的随机映射。

令 k=n+1 代入 Newton 恒等式整理得

p_{n+1}=\sum_{i=1}^{n} (-1)^{i-1} e_ip_{n+1-i}

上式给出 p_1 \sim p_{n+1} 是 n 个数幂和的必要条件。

不妨设 S_v \subset S_u,差集哈希

\begin{aligned} H_i(S_u \setminus S_v)&=H_i(S_u)-H_i(S_v)\\ &=\sum _{x \in S_u \setminus S_v} h^i(x) \end{aligned}

必然是 |S_u|-|S_v| 个数的幂和,可以通过 Newton 恒等式检验。反之,哈希作差只是若干正项减去若干负项,极大概率无法通过检验。

实际检验时,我们声称 p_1 \sim p_{n+1} 是幂和,递推出 e_1\sim e_n 后代入公式检查即可。只要用数据结构维护 k+1 个幂和。

开 k+1 个差分树状数组,支持区间加单点查询。朴素实现 O(qk \log n+qk^2),多项式 \exp 可优化到 O(qk \log k)。

const int N = 2e6 + 5;
int n, q, k;
umap<i64, mint> mp;
mint h(i64 x) {
    if (mp.find(x) != mp.end()) return mp[x];
    return mp[x] = rand64();
}

template <class mint>
struct BIT {
    mint *a;
    void init() {
        a = new mint[n + 5];
        memset(a, 0, sizeof(mint) * (n+5));
    }
    void add(int x, mint c) {
        for (; x <= n; x += lowbit(x)) a[x] += c;
    }
    void add(int l, int r, mint c) {
        add(l, c), add(r+1, -c);
    }
    mint ask(int x) {
        mint res = 0;
        for (; x >= 1; x -= lowbit(x)) res += a[x];
        return res;
    }
};
BIT<int> S;
BIT<mint> T[32];

mint inv[40], p[40], e[40];
bool check(int x, int y, int n) {
    // y is subset of x
    for (int i = 1; i <= n+1; i++)
        p[i] = T[i].ask(x) - T[i].ask(y);
    fill(e + 1, e + n + 2, 0), e[0] = 1;
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= k; i++) {
            if (i & 1) e[k] += e[k-i] * p[i];
            else e[k] -= e[k-i] * p[i];
        }
        e[k] *= inv[k];
    }
    mint res = 0;
    for (int i = 1; i <= n; i++) 
        if (i & 1) res += e[i] * p[n+1-i];
        else res -= e[i] * p[n+1-i];
    return res == p[n+1];
} 

void _main() {
    cin >> n >> q >> k; S.init();
    for (int i = 1; i <= k+1; i++) inv[i] = ~mint(i), T[i].init();
    for (i64 op, l, r, x, y; q--; ) {
        cin >> op;
        if (op == 1) {
            cin >> l >> r >> x;
            S.add(l, r, 1);
            mint h0 = h(x), hi = h0;
            for (int i = 1; i <= k+1; i++, hi *= h0) 
                T[i].add(l, r, hi);
        } else if (op == 2) {
            cin >> l >> r >> x;
            S.add(l, r, -1);
            mint h0 = h(x), hi = h0;
            for (int i = 1; i <= k+1; i++, hi *= h0) 
                T[i].add(l, r, -hi);
        } else {
            cin >> x >> y;
            int w = 4, s1 = S.ask(x), s2 = S.ask(y);
            if (s1 == s2 && T[1].ask(x) == T[1].ask(y)) w = 3;
            else if (s1 < s2 && check(y, x, s2 - s1)) w = 2;
            else if (s1 > s2 && check(x, y, s1 - s2)) w = 1;
            cout << w << '\n';
        }
    }
}