自动搬运

查看原文

来自洛谷，原作者为

	Rubidium_Chloride No, I can't.

搬运于2025-08-24 22:18:36，当前版本为作者最后更新于2020-03-26 11:45:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这题是数论题吧。

0.前言

请容许我无耻地放一下我的博客的链接……

接下来，让我们进入正题。

1.分析题目

1.1 题目大意

题目传送门

即求$\sum\limits_{i=1}^{n}(b_i\times\sum\limits_{1\le j_1< j_2<...< j_i\le n}x_{j_1} x_{j_2}\dots x_{j_i})------(1)$

其中$x_1,x_2...x_n$为$n$次方程$x^n+a_1x^{n-1}+a_2x^{n-2}+...+a_n=0$的$n$个复数范围内的根。

1.2 分析做法

仔细想想，什么东西有和$(1)$有相同/类似的性质呢？

本蒟蒻前想后想，终于想出了一个相同的东西：韦达定理。

（话说提示里不是有吗？）

2.韦达定理

如果您还不知道伟大韦达定理，珂以看这里。

证明如下：

由于代数基本定理，有$x_1,x_2\dots x_n$是$a_0x^n+a_1x^{n-1}+\dots+a_n=0$的$n$个复数根。

那么根据因式分解基本常识，可以得到$a_0(x-x_1)(x-x_2)\dots(x-x_n)=0------(2)$

这个方程的$n$个复数根和$(1)$的$n$个根一模一样。

所以可以得到：$(2)$与$(1)$是同一个方程！

将$(2)$展开，得：

$a_0x^n-a_0(\sum\limits_{1\le i\le n}x_i)x^{n-1}+a_0(\sum\limits_{1\le i_1< i_2\le n}x_{i_1}x_{i_2})x^{n-2}\dots+(-1)^na_0\prod\limits_{i=1}^{n}x_i$

其各项系数应该与$(1)$的各项系数相同。

于是可得以下等式：

$\begin{cases}a_0(\sum\limits_{1\le i\le n}x_i)=a_1\\a_0(\sum\limits_{1\le i_1< i_2\le n}x_{i_1}x_{i_2})=a_2\\\dots\\(-1)^na_0\prod\limits_{i=1}^{n}x_i=a_n\end{cases}$

将每行等式同时除以$a_0$即得韦达定理最终形式：

$\begin{cases}\sum\limits_{1\le i\le n}x_i=\frac{a_1}{a_0}\\\sum\limits_{1\le i_1< i_2\le n}x_{i_1}x_{i_2}=\frac{a_2}{a_0}\\\dots\\\prod\limits_{i=1}^{n}x_i=(-1)^n\frac{a_n}{a_0}\end{cases}$

这不就和题目要我们求的东西差不多嘛？

3.最后分析与Code

（没错，你们最爱的代码君将在若干行后到达题解）

由第$2$部分的证明，我们得到了题目让我们求的东西就是:

$\sum\limits_{i=1}^{n}(-1)^ia_ib_i$

所以我们就有了如下的代码：

#include<bits/stdc++.h>
#define N 200009
using namespace std;
typedef long long ll;
ll n,a[N],b[N],ans,flag=1;
const ll MOD=1e9+7;
inline int read(){//写了一个快读卡常 
	int x=0;int f=1;int c=getchar();
    while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++){
		flag*=-1;//flag就是用来计算(-1)^n的 
		b[i]=read();
		ans+=(a[i]*b[i]*flag);ans%=MOD;
	}
	printf("%lld",(ans+MOD)%MOD);//别忘了最后负数取模！ 
	return 0;
//}禁止抄袭！

4.后记

看我这么努力地写了这篇通俗易懂的题解，还附上了十分具体的证明，您不给我点个赞吗？

最后的最后，管理大大求过。