MCOI R6 C 题解

· · 题解

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 进行一些判断：