自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 22:33:58，当前版本为作者最后更新于2021-10-04 21:13:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

Description

求序列 $a_1,a_2,\dots,a_n$ 使得对于所有 $i=1,2,\dots,n$ 有：

$$x_i\left(\sum_{j=1}^ia_i\right)+y_i\left(\sum_{j=i}^na_i\right)\equiv z_i\pmod{10^9+7} $$

Solution

誊抄官方题解 我们直接不考虑 $\bmod 10^9+7$，因此以下运算在模 $10^9+7$ 意义下进行。

考虑 $a_i$ 的前缀和 $S_i$，则题目中的要求可以表示为（$i \in (1,n]$）：

$$\begin{aligned}x_iS_i+y_i(S_n-S_{i-1})&=z_i\\x_iS_i+y_iS_n-y_iS_{i-1}&=z_i\\x_iS_i-y_iS_{i-1}&=z_i-y_iS_n\end{aligned} $$

对于 $i=1$ 即为：

$$\begin{aligned}x_1a_1+y_1S_n&=z_1\\S_n&=\frac{z_1-x_1a_1}{y_1}\end{aligned} $$

代入 $i \in (1,n]$ 的情况则有：

$$\begin{aligned}x_iS_i-y_iS_{i-1}&=z_i-y_i\frac{z_1-x_1a_1}{y_1}\\S_i&=\frac{z_i+y_i\left(S_{i-1}-\frac{z_1-x_1a_1}{y_1}\right)}{x_i}\end{aligned} $$

不难得知，所有 $S_i$ 都可以表示为 $A_ia_1+B_i$（因为 $S_1=a_1$），我们考虑求出 $A_i$ 与 $B_i$：

$$\begin{aligned}S_i&=\frac{z_i+y_i(A_{i-1}a_1+B_{i-1}-\frac{z_1-x_1a_1}{y_1})}{x_i}\\S_i&=\frac{y_i}{x_i}A_{i-1}a_1+\frac{z_i}{x_i}+\frac{y_i}{x_i}B_{i-1}-\frac{z_1y_i}{y_1x_i}+\frac{x_1y_i}{y_1x_i}a_1\\S_i&=\frac{y_i}{x_i}\left(A_{i-1}+\frac{x_1}{y_1}\right)a_1+\frac{z_i}{x_i}+\frac{y_i}{x_i}\left(B_{i-1}-\frac{z_1}{y_1}\right)\end{aligned} $$

因此：

$$\begin{aligned}A_i&=\frac{y_i}{x_i}\left(A_{i-1}+\frac{x_1}{y_1}\right)\\B_i&=\frac{z_i}{x_i}+\frac{y_i}{x_i}\left(B_{i-1}-\frac{z_1}{y_1}\right)\end{aligned} $$

求出 $S_n$ 后代入 $S_n=\frac{z_1-x_1a_1}{y_1}$ 就可以得到 $a_1$ 了。

对 $a_1$ 进行一些判断：

• 如果 $a_1=\frac 0 0$，则任意 $a_1$ 都满足，解数为 $10^9+7$；
• 如果 $a_1=\frac x 0\ (x \ne 0)$，则没有 $a_1$ 满足，解数为 $0$；
• 其他情况都有解。