【数学随记】浅谈牛顿恒等式及其应用

· · 算法·理论

前言

在 4 月份的时候打模拟赛，遇到了一道求排列乘积和的题。正解实际上是用线段树做的，但是太难了 QWQ，于是就有了这篇文章（部分内容摘自 DeepSeek）。蒟蒻写得烂，不喜勿喷（）

牛顿恒等式（Newton's Identities）可以在 OI 中解决一类求一个序列有序/无序选取 k 个不同变量的乘积之和的问题（前提是 k 很小），其实本质上是容斥的一种形式，在组合数学与物理学等方面都有广泛应用。

前置知识

初等对称多项式 \sigma_k 定义为从一个长度为 n 的序列 x_1,x_2,\cdots,x_n 中无序选取 k 个不同变量的乘积之和。特别地，\sigma_0=1，如

\sigma_1=\sum_{i=1}^nx_i,\sigma_2=\sum_{1\le i<j\le n}x_ix_j,\sigma_3=\sum_{1\le i<j<k\le n}x_ix_jx_k

幂和对称多项式 s_k 定义为所有 n 个变量 x_1,x_2,\cdots,x_n 的 k 次幂之和，即

s_k=\sum_{i=1}^nx_i^k

导数描述的是函数在某一点的瞬时变化率（可以理解为加速度），具体地，对一个函数 f(x)，其导数 f'(x)（等价于 \dfrac{\mathrm{d}}{\mathrm{d}x}f(x)）定义为

f'(x)=\lim_{\Delta x\rightarrow 0}\frac{f(x+\Delta x)-f(x)}{\Delta x}

生成函数是一种将序列编码为多项式系数的方法，如对于序列 x_0,x_1,\cdots,x_n，其普通生成函数（OGF） 为

G(t)=\sum_{i=0}^nx_it^i

牛顿恒等式及其证明

牛顿恒等式

\sigma_k=\frac{1}{k}\sum_{i=1}^k(-1)^{i-1}\sigma_{k-i}s_i

证明

首先写出 \sigma 的 OGF。

\Sigma(t)=\sum_{k=0}^n\sigma_kt^k=\prod_{k=1}^n(x_kt+1)

为了与 s_k 有联系，我们对 \ln\Sigma(t) 求导。

\frac{\mathrm{d}}{\mathrm{d}t}\ln\Sigma(t)=\frac{\mathrm{d}}{\mathrm{d}\Sigma(t)}\ln\Sigma(t)\cdot\frac{\mathrm{d}}{\mathrm{d}t}\Sigma(t)=\frac{1}{\Sigma(t)}\cdot \Sigma'(t)=\frac{\Sigma'(t)}{\Sigma(t)}

又因为 \displaystyle\ln\Sigma(t)=\sum_{i=1}^n\ln(x_it+1)，所以

\begin{aligned}\frac{\mathrm{d}}{\mathrm{d}t}\ln\Sigma(t)&=\sum_{i=1}^n\frac{\mathrm{d}}{\mathrm{d}t}\ln(x_it+1)=\sum_{i=1}^n\frac{\mathrm{d}}{\mathrm{d}\ln(x_it+1)}\ln(x_it+1)\cdot\frac{\mathrm{d}}{\mathrm{d}t}(x_it+1)\\&=\sum_{i=1}^n\frac{1}{x_it+1}\cdot x_i=\sum_{i=1}^n\frac{x_i}{x_it+1}\end{aligned}

即

\boxed{\frac{\Sigma'(t)}{\Sigma(t)}=\sum_{i=1}^n\frac{x_i}{x_it+1}}

然后将 \dfrac{x_i}{x_it+1} 展开为无穷级数。

\frac{x_i}{x_it+1}=x_i\cdot\frac{1}{x_it+1}=x_i\sum_{n=0}^\infin(-x_it)^n=\sum_{n=0}^\infin(-1)^nx_i^{n+1}t^n

所以

\frac{\Sigma'(t)}{\Sigma(t)}=\sum_{k=0}^\infin(-1)^k\left(\sum_{i=1}^nx_i^{k+1}\right)t^k=\sum_{k=0}^\infin(-1)^ks_{k+1}t^k

又因为 \displaystyle\Sigma(t)=\sum_{k=0}^n\sigma_kt^k，所以

\Sigma'(t)=\sum_{k=1}^nk\sigma_kt^{k-1}=\Sigma(t)\cdot\frac{\Sigma'(t)}{\Sigma(t)}=\left(\sum_{k=0}^n\sigma_kt^k\right)\left[\sum_{k=0}^\infin(-1)^ks_{k+1}t^k\right]

即

\sum_{k=1}^nk\sigma_kt^{k-1}=\left(\sum_{k=0}^n\sigma_kt^k\right)\left[\sum_{k=0}^\infin(-1)^ks_{k+1}t^k\right]

消去两边 t 值可化简得

k\sigma_k=\sum_{i=0}^{k-1}(-1)^i\sigma_{k-i-1}s_{i+1}=\sum_{i=1}^k(-1)^{i-1} \sigma_{k-i}s_i

即

\boxed{\sigma_k=\frac{1}{k}\sum_{i=1}^k(-1)^{i-1}\sigma_{k-i}s_i}

得证。

拓展（线性代数与高等数学内容，可略过）

我们可以利用行列式求出 \sigma_k 的通项公式。具体地，先写出 \ln\Sigma(t) 的 OGF。

F(t)=\sum_{k=1}^\infin(-1)^{k-1}\frac{s_k}{k}t^k=\sum_{k=1}^n\ln(x_kt+1)

而因为

\Sigma(t)=\sum_{k=0}^n\sigma_kt^k=\prod_{k=1}^n(x_kt+1)

所以可通过指数函数 \exp 关联起来，即

\sum_{k=0}^n\sigma_kt^k=\exp\left[\sum_{k=1}^\infin(-1)^{k-1}\frac{s_k}{k}t^k\right]

然后对这个指数函数进行泰勒展开，将得到的系数组成一个 k\times k 的行列式。

|A|_k=\begin{vmatrix}s_1&1&0&0&\cdots&0\\s_2&s_1&2&0&\cdots&0\\s_3&s_2&s_1&3&\cdots&0\\s_4&s_3&s_2&s_1&\cdots&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\s_{k-1}&s_{k-2}&s_{k-3}&s_{k-4}&\cdots&k-1\\s_k&s_{k-1}&s_{k-2}&s_{k-3}&\cdots&s_1\end{vmatrix}

即其元素 a_{i,j} 定义为

\boxed{a_{i,j}=\begin{cases}s_{i-j+1},&i\ge j\\j-1,&i=j-1\\0,&i<j-1\end{cases}}

于是即有通项公式

\boxed{\sigma_k=\frac{1}{k!}\cdot A_k}

例如当 k=3 时，则有

\begin{aligned}\sigma_3&=\frac{1}{3!}\begin{vmatrix}s_1&1&0\\s_2&s_1&2\\s_3&s_2&s_1\end{vmatrix}=\frac{1}{6}\left(s_1\begin{vmatrix}s_1&2\\s_2&s_1\end{vmatrix}-1\begin{vmatrix}s_2&2\\s_3&s_1\end{vmatrix}+0\begin{vmatrix}s_2&s_1\\s_3&s_2\end{vmatrix}\right)\\&=\frac{1}{6}\left[s_1\left(s_1^2-2s_2\right)-(s_1s_2-2s_3)\right]=\frac{1}{6}\left(s_1^3-3s_1s_2+2s_3\right)\end{aligned}

例题

【NOIP2015 五校联考模拟赛 5 Day 1】Melancholy

形式化题意：给定 N 个数对 (D_i,V_i) 和 Q 次查询，每次查询给定一个查询区间 [L,R] 和 K，问在所有满足 D_i\in[L,R] 的 V_i 中选出 K 个的所有排列（满足不含这其中最小的 V_i）的价值和，其中一个排列的价值定义为排列中所有数的乘积，答案对 2^{32} 取模，特别地，若无解则输出 0。数据范围 N,Q\le 10^5,K\le 6，保证所有 D_i,V_i 互不相等。

解题思路

首先转换一下题意，就是要求从一个序列 V_1,V_2,\cdots,V_m 中有序选取 K 个不同变量的乘积之和，于是考虑使用牛顿恒等式。又惊奇地发现 K\le 6，所以可以暴力求出所有的 \sigma_K。即通过 \sigma_0=1 可得

\begin{aligned}\sigma_1&=s_1,\sigma_2=\frac{1}{2}\left(s_1^2-s_2\right),\sigma_3=\frac{1}{6}\left(s_1^3-3s_1s_2+2s_3\right),\\\sigma_4&=\frac{1}{24}\left(s_1^4-6s_1^2s_2+8s_1s_3+3s_2^2-6s_4\right),\\\sigma_5&=\frac{1}{120}\left(s_1^5-10s_1^3s_2+15s_1s_2^2+20s_1^2s_3-30s_1s_4-20s_2s_3+24s_5\right),\\\sigma_6&=\frac{1}{720}\left(s_1^6-15s_1^4s_2+45s_1^2s_2^2-120s_1s_2s_3+40s_1^3s_3-90s_1^2s_4+144s_1s_5-15s_2^3+90s_2s_4+40s_3^2-120s_6\right)\end{aligned}

而最终答案因为是有序选取，故答案 ans_K=K!\sigma_K。综上，我们只需先把 V_i 按照 D_i 的值从小到大排序，然后预处理出未去除最小值（即所有 V_i）的 s_i（类似于前缀和）和最小值 ST 表。对于每次询问，先通过两次二分得出 [L,R] 对应的 V_i 区间（这里要判是否无解），再查询区间最小值，临时更新一下 s_i，最后直接套用上面答案的公式即可，时间复杂度 O((N+Q)\log N)。

AC 代码

#include <bits/stdc++.h>
#define ll unsigned int
#define endl putchar(10)
#define R register
using namespace std;

// 快读快输
inline ll read()
{
    ll x=0,f=1; char c=getchar();

    while(c<48 || c>57)
    {
        if(c=='-') f=-1;
        c=getchar();
    }

    while(c>47 && c<58)
    x=(x<<1)+(x<<3)+c-48, c=getchar();
    return x*f;
}

inline void write(ll x)
{
    static ll st[41]; ll tp=0;
    if(x<0) putchar('-'), x=-x;
    do st[tp++]=x%10, x/=10; while(x);
    while(tp) putchar(st[--tp]+48);
}

ll n,q,x,y,k,l,r,mid,f[100001][18],lg[100001],
d[100001],v[100001],sum[100001][7],s[7],mn,ans;

// 快速幂，用来预处理 s[i]
ll qpow(ll x, ll y)
{
    ll res=1;

    while(y)
    {
        if(y&1) res*=x;
        x*=x; y>>=1;
    }

    return res;
}

// 将 D[i] 和 V[i] 按照 D[i] 为关键字从小到大排序
void qsort(ll l, ll r)
{
    if(l>=r) return;
    ll i=l, j=r, p=d[l+r>>1];

    while(i<=j)
    {
        while(d[i]<p) ++i;
        while(d[j]>p) --j;
        if(i<=j) swap(d[i],d[j]), swap(v[i++],v[j--]);
    }

    qsort(l,i-1); qsort(i,r);
}

int main()
{
    n=read(); q=read();
    for(R ll i=2; i<=n; ++i) lg[i]=lg[i>>1]+1; // 预处理 log
    for(R ll i=1; i<=n; ++i) d[i]=read();
    for(R ll i=1; i<=n; ++i) v[i]=read();
    qsort(1,n); // 排序

    // 预处理 s[i]
    for(R ll i=1; i<=n; ++i)
    {
        f[i][0]=v[i];
        for(R ll j=1; j<7; ++j) sum[i][j]=sum[i-1][j]+qpow(v[i],j);
    }

    // ST 表预处理
    for(R ll i=1; i<=lg[n]; ++i)
    {
        for(R ll j=1; j<=n-(1<<i)+1; ++j)
        f[j][i]=min(f[j][i-1],f[j+(1<<i-1)][i-1]);
    }

    while(q--)
    {
        x=read(); y=read(); k=read();
        l=0; r=n+1;

        // 二分找到 [L,R] 对应区间
        while(l<r-1)
        {
            mid=l+r>>1;
            if(d[mid]<x) l=mid;
            else r=mid;
        }

        x=r; l=0; r=n+1;

        while(l<r-1)
        {
            mid=l+r>>1;
            if(d[mid]>y) r=mid;
            else l=mid;
        }

        y=l; // [L,R] 对应区间即为 [x,y]

        // 判无解
        if(x>y)
        {
            write(0); endl; continue;
        }

        // 找到最小值
        l=lg[y-x+1]; mn=min(f[x][l],f[y-(1<<l)+1][l]);

        // 重新更新 s[i]
        for(R int i=1; i<=k; ++i)
        s[i]=sum[y][i]-sum[x-1][i]-qpow(mn,i);

        // 套公式直接计算答案
        if(k<2) write(s[1]);

        else if(k<3) write(s[1]*s[1]-s[2]);

        else if(k<4) write(s[1]*s[1]*s[1]-s[1]*s[2]*3+s[3]*2);

        else if(k<5) write(s[1]*s[1]*s[1]*s[1]-
        s[1]*s[1]*s[2]*6+s[1]*s[3]*8+s[2]*s[2]*3-s[4]*6);

        else if(k<6) write(s[1]*s[1]*s[1]*s[1]*s[1]-
        s[1]*s[1]*s[1]*s[2]*10+s[1]*s[2]*s[2]*15+
        s[1]*s[1]*s[3]*20-s[1]*s[4]*30-s[2]*s[3]*20+s[5]*24);

        else write(s[1]*s[1]*s[1]*s[1]*s[1]*s[1]-
        s[1]*s[1]*s[1]*s[1]*s[2]*15+s[1]*s[1]*s[2]*s[2]*45-
        s[1]*s[2]*s[3]*120+s[1]*s[1]*s[1]*s[3]*40-s[1]*s[1]*s[4]*90+
        s[1]*s[5]*144-s[2]*s[2]*s[2]*15+s[2]*s[4]*90+s[3]*s[3]*40-s[6]*120);

        endl;
    }

    return 0;
}