自动搬运

查看原文

来自洛谷，原作者为

	0x3F Wir müssen wissen, wir werden wissen.

搬运于2025-08-24 22:06:59，当前版本为作者最后更新于2021-02-15 23:23:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

发现 $n \leqslant 4$ 。

所以分类讨论即可。

我们令 $s_i$ 等于这些字母的 $i$ 次方和。

当 $n = 1$ 时， $s_i = a_1^i$ , 即 $s_i = \begin{cases} 1&i = 0 \\ a_1 \times s_{i-1} & i > 0\end{cases}$

当 $n = 2$ 时， $s_0 = 2$ ， $s_1 = a_1$ ， $s_2 , s_3$ 等虽然都能求，但是 $s_i$ 怎么求呢？

或者说， $s_i$ 如何通过已经求出的 $s_{0,1,\dots,i-1}$ 来求呢？

这里给大家提供一个很新颖的方法：韦达定理。

当 $i > 1$ 时，由韦达定理我们得到：

$$\begin{cases} x^2 - a_1x + a_2 = 0\qquad(1)\\ y^2 - a_1y + a_2 = 0\qquad(2)\end{cases} $$

$(1)$ 式乘以 $x^{i-2}$ ， $(2)$ 式乘以 $y^{i-2}$ ，得到

$$\begin{cases} x^i - a_1x^{i-1} + a_2x^{i-2} = 0\\ y^i - a_1y^{i-1} + a_2y^{i-2} = 0\end{cases} $$

两式相加，得到

$$x^i + y^i - a_1(x^{i-1} + y^{i-1}) + a_2(x^{i-2} + y^{i-2}) = 0 $$

即 $s_i - a_1s_{i-1} + a_2s_{i-2} = 0$ 。

所以： $s_i = \begin{cases} 2&i = 0 \\ a_1&i = 1 \\ a_1 \times s_{i-1} - a_2 \times s_{i-2}& i > 1\end{cases}$

当 $n = 3$ 时，

$$s_0 = 3, s_1 = a_1$$ $$s_2 = x^2 + y^2 + z^2$$ $$= (x + y + z)^2 - 2 (xy + xz + yz)$$ $$= a_1^2 - 2a_2$$

同样使用韦达定理，得：当 $i > 2$ 时，

$$s_i = a_1 \times s_{i-1} - a_2 \times s_{i-2} + a_3 \times s_{i-3} $$

所以： $s_i = \begin{cases} 3&i = 0 \\ a_1&i = 1 \\ a_1^2 - 2a_2&i = 2 \\ a_1 \times s_{i-1} - a_2 \times s_{i-2} + a_3 \times s_{i-3}& i > 2\end{cases}$

当 $n = 4$ 时，

$$s_0 = 4, s_1 = a_1, s_2 = a_1^2 - 2a_2$$

$s_3$ 的柿子就比较难了。

首先考虑$a_1^3$ , 将其暴力展开得：

$$a_1^3 = (x + y + z + u)^3$$ $$=(x^3 + y^3 + z^3 + u^3)$$ $$+ 3 (x^2y + x^2z + x^2u + y^2x + y^2z + y^2u + z^2x + z^2y + z^2u + u^2x + u^2y + u^2z) $$$$+ 6 (xyz + xyu + xzu + yzu)$$

尝试将第二项消掉。

我们发现， $a_1a_2=$

$$(x+y+z+u)(xy+xz+xu+yz+yu+zu)$$ $$= (x^2y + x^2z + x^2u + y^2x + y^2z + y^2u + z^2x + z^2y + z^2u + u^2x + u^2y + u^2z) $$$$+ 3 (xyz + xyu + xzu + yzu)$$

将其乘以 $3$ ，用它减一下上式， 得到：

$$a_1^3 - 3a_1a_2 = (x^3 + y^3 + z^3 + u^3) - 3(xyz + xyu + xzu + yzu) $$

代入，移项，得

$$a_1^3 - 3a_1a_2 + 3a_3= s_3$$

再使用一次韦达定理，得：当 $i > 3$ 时，

$$s_i = a_1 \times s_{i-1} - a_2 \times s_{i-2} + a_3 \times s_{i-3} - a_4 \times s_{i-4} $$

所以： $s_i = \begin{cases} 4&i = 0 \\ a_1&i = 1 \\ a_1^2 - 2a_2&i = 2 \\ a_1^3 - 3a_1a_2 + 3a_3&i = 3 \\ a_1 \times s_{i-1} - a_2 \times s_{i-2} + a_3 \times s_{i-3} - a_4 \times s_{i-4}& i > 3\end{cases}$

不要忘了取模！！！

还有，十年 $OI$ 一场空，不开 long long 见祖宗！！！

另外，负数要转正！！！

不多说了，上代码：

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e7 + 29;
int n, m, x, y, z, u;
long long arr[100010];
int main() {
	cin >> n >> m;
	arr[0] = n;
	switch (n) {
		case 1: {
			cin >> x;
			for (int i = 1; i <= m; i++) {
				arr[i] = arr[i-1] * x;
				arr[i] = (arr[i] % mod + mod) % mod;
			}
			break;
		}
		case 2: {
			cin >> x >> y;
			arr[1] = x;
			for (int i = 2; i <= m; i++) {
				arr[i] = arr[i-1] * x - arr[i-2] * y;
				arr[i] = (arr[i] % mod + mod) % mod;
			}
			break;
		}
		case 3: {
			cin >> x >> y >> z;
			arr[1] = x;
			arr[2] = x*x - 2*y;
			arr[2] = (arr[2] % mod + mod) % mod;
			for (int i = 3; i <= m; i++) {
				arr[i] = arr[i-1] * x - arr[i-2] * y + arr[i-3] * z;
				arr[i] = (arr[i] % mod + mod) % mod;
			}
			break;
		}
		case 4: {
			cin >> x >> y >> z >> u;
			arr[1] = x;
			arr[2] = x*x - 2*y;
			arr[2] = (arr[2] % mod + mod) % mod;
			arr[3] = (long long)x*x*x - 3*x*y + 3*z;
			arr[3] = (arr[3] % mod + mod) % mod;
			for (int i = 4; i <= m; i++) {
				arr[i] = arr[i-1] * x - arr[i-2] * y + arr[i-3] * z - arr[i-4] * u;
				arr[i] = (arr[i] % mod + mod) % mod;
			}
			break;
		}
	}
	cout << arr[m] << endl;
	return 0;
}

看在我打 $\LaTeX$ 这么辛苦的份上，点个赞再走吧！