专栏文章

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

JJXR_Kalcium
算法·理论参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mio82egm
此快照首次捕获于
2025/12/02 14:53
3 个月前
此快照最后确认于
2025/12/02 14:53
3 个月前
查看原文

前言

在 44 月份的时候打模拟赛，遇到了一道求排列乘积和的题。正解实际上是用线段树做的，但是太难了 QWQ，于是就有了这篇文章（部分内容摘自 DeepSeek）。蒟蒻写得烂，不喜勿喷（）
牛顿恒等式（Newton's Identities）可以在 OI 中解决一类求一个序列有序/无序选取 kk 个不同变量的乘积之和的问题（前提是 kk 很小），其实本质上是容斥的一种形式，在组合数学与物理学等方面都有广泛应用。

前置知识

初等对称多项式 σk\sigma_k 定义为从一个长度为 nn 的序列 x1,x2,⋯ ,xnx_1,x_2,\cdots,x_n 中无序选取 kk 个不同变量的乘积之和。特别地，σ0=1\sigma_0=1，如
σ1=∑i=1nxi,σ2=∑1≤i<j≤nxixj,σ3=∑1≤i<j<k≤nxixjxk\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
幂和对称多项式 sks_k 定义为所有 nn 个变量 x1,x2,⋯ ,xnx_1,x_2,\cdots,x_n 的 kk 次幂之和，即
sk=∑i=1nxiks_k=\sum_{i=1}^nx_i^k
导数描述的是函数在某一点的瞬时变化率（可以理解为加速度），具体地，对一个函数 f(x)f(x)，其导数 f′(x)f'(x)（等价于 ddxf(x)\dfrac{\mathrm{d}}{\mathrm{d}x}f(x)）定义为
f′(x)=lim⁡Δx→0f(x+Δx)−f(x)Δxf'(x)=\lim_{\Delta x\rightarrow 0}\frac{f(x+\Delta x)-f(x)}{\Delta x}
生成函数是一种将序列编码为多项式系数的方法，如对于序列 x0,x1,⋯ ,xnx_0,x_1,\cdots,x_n，其普通生成函数（OGF） 为
G(t)=∑i=0nxitiG(t)=\sum_{i=0}^nx_it^i

牛顿恒等式及其证明

牛顿恒等式

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

证明

首先写出 σ\sigma 的 OGF。
Σ(t)=∑k=0nσktk=∏k=1n(xkt+1)\Sigma(t)=\sum_{k=0}^n\sigma_kt^k=\prod_{k=1}^n(x_kt+1)
为了与 sks_k 有联系，我们对 ln⁡Σ(t)\ln\Sigma(t) 求导。
ddtln⁡Σ(t)=ddΣ(t)ln⁡Σ(t)⋅ddtΣ(t)=1Σ(t)⋅Σ′(t)=Σ′(t)Σ(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)}
又因为 ln⁡Σ(t)=∑i=1nln⁡(xit+1)\displaystyle\ln\Sigma(t)=\sum_{i=1}^n\ln(x_it+1)，所以
ddtln⁡Σ(t)=∑i=1nddtln⁡(xit+1)=∑i=1nddln⁡(xit+1)ln⁡(xit+1)⋅ddt(xit+1)=∑i=1n1xit+1⋅xi=∑i=1nxixit+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}
即
Σ′(t)Σ(t)=∑i=1nxixit+1\boxed{\frac{\Sigma'(t)}{\Sigma(t)}=\sum_{i=1}^n\frac{x_i}{x_it+1}}
然后将 xixit+1\dfrac{x_i}{x_it+1} 展开为无穷级数。
xixit+1=xi⋅1xit+1=xi∑n=0∞(−xit)n=∑n=0∞(−1)nxin+1tn\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
所以
Σ′(t)Σ(t)=∑k=0∞(−1)k(∑i=1nxik+1)tk=∑k=0∞(−1)ksk+1tk\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
又因为 Σ(t)=∑k=0nσktk\displaystyle\Sigma(t)=\sum_{k=0}^n\sigma_kt^k，所以
Σ′(t)=∑k=1nkσktk−1=Σ(t)⋅Σ′(t)Σ(t)=(∑k=0nσktk)[∑k=0∞(−1)ksk+1tk]\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]
即
∑k=1nkσktk−1=(∑k=0nσktk)[∑k=0∞(−1)ksk+1tk]\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]
消去两边 tt 值可化简得
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 代码 ```cpp #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; } ```

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...