题解 P6211 【「SWTR-04」Meeting in the Forest】

· · 题解

这题是数论题吧。

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.后记

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

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