题解 P5084 【轮换式】

· · 题解

发现 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} $$\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 首先考虑$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 这么辛苦的份上，点个赞再走吧！