题目来源
【LGR-093】洛谷 10 月月赛 I & MCOI R6 Div.1 A题
【LGR-093】洛谷 10 月月赛 I & MCOI R6 Div.2 C题
题意
可能存在一个非负整数数序列 $a_1,a_2,\dots,a_n$ 使得 $0\leq a_i < 10^9+7$。
给定 $x_1,x_2,\cdots,x_n$，$y_1,y_2,\cdots,y_n$，$z_1,z_2,\cdots,z_n$，已知对于 $1\le i\le n$ 满足：
x_i\left(\sum_{j=1}^ia_j\right)+y_i\left(\sum_{j=i}^na_j\right)\equiv z_i\pmod{10^9+7}
$$
先求满足条件的解的个数。若只有一组解，求出 $a_1,a_2,\dots,a_n$。
有多测。
对于 $10\%$ 的数据，$n=1$，
对于另外 $19\%$ 的数据，$n\leq 100$，
对于另外 $19\%$ 的数据，$x_i=y_i=1$，
对于另外 $22\%$ 的数据，保证有唯一解。
对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\leq x_i, y_i\leq 10^9+7$，$0\leq z_i\leq 10^9+7$.
$\rm{Subtask}$ $1$
对于 $10\%$ 的数据，$n=1$.
按照题意写出关于 $a_1$ 的方程：
x_1a_1+y_1a_1\equiv z_1 \pmod{10^9+7}
$$
即：
(x_1+y_1)a_1\equiv z_1\pmod{10^9+7}
$$
注意到此时 $a_1$ 不一定有唯一解，需要分类讨论。
一、 当 $x_1+y_1=0$ 且 $z_1\neq 0$ 时，方程无解。
二、 当 $x_1+y_1=0$ 且 $z_1=0$ 时，$a_1$ 可以在 $[0, 10^9+7)$ 上任取，共有 $10^9+7$ 组解。
三、 对于其他情况均有唯一解：
a_1=\frac{z_1}{x_1+y_1}\pmod{10^9+7}
$$
用乘法逆元处理即可。
if(n == 1) cout << 1 << endl << z[1] * inv((x[1] + y[1]) % mod) % mod << endl;
这里如果只考虑情况三，也可以拿到这 $10$ 分。
但由于题目有多组测试数据，如果后续在代码中保留对 $n=1$ 的特判，不分类讨论会被卡掉。
然后还查不出来）
$\rm{Subtask}$ $3$
对于另外 $19 \%$ 的数据，$x_i=y_i=1$.
为了方便表示，后面涉及的所有运算都在 $\bmod 10^9+7$ 意义下进行。
把 $n$ 个方程列出：
\left \{
\begin{array}{l}
x_1(a_1)+y_1(a_1+a_2+\cdots+a_n)=z_1\\
x_2(a_1+a_2)+y_2(a_2+\cdots+a_n)=z_2\\
x_3(a_1+\cdots+a_3)+y_3(a_3+\cdots+a_n)=z_3\\
\cdots\\
x_n(a_1+a_2+\cdots+a_n)+y_n(a_n)=z_n\\
\end{array}
\right.
$$
若 $x_i=y_i=1$，那么：
\left\{
\begin{array}{l}
(a_1+a_2+\cdots+a_n)+a_1=z_1 &(1)\\
(a_1+a_2+\cdots+a_n)+a_2=z_2 &(2)\\
(a_1+a_2+\cdots+a_n)+a_3=z_3 &(3)\\
\cdots&\cdots\\
(a_1+a_2+\cdots+a_n)+a_n=z_n &(n)\\
\end{array}
\right.
$$
容易想到把 $n$ 个方程相加，
(n+1)(a_1+a_2+\cdots+a_n)=z_1+z_2+\cdots+z_n
$$
把 $n+1$ 除过去就能得到 $a_1+a_2+\cdots+a_n$ 的值，再代入 $(1)\cdots(n)$ 式即可求出答案。
同样的，需要分类讨论一下解的情况。但对于这部分数据，不讨论也能通过。
if(subtask3) {
int sumz = 0;
for(int i = 1; i <= n; i++) (sumz += z[i]) %= mod;
int sum = sumz * inv(n + 1) % mod;
cout << 1 << endl;
for(int i = 1; i <= n; i++) {
cout << (((z[i] - sum) % mod) + mod) % mod << " ";
} cout << endl;
}
$\rm{Subtask}$ $2$
对于另外 $19\%$ 的数据，$n\leq 100$。
\left\{
\begin{array}{}
x_1(a_1)+y_1(a_1+a_2+\cdots+a_n)=z_1\\
x_2(a_1+a_2)+y_2(a_2+\cdots+a_n)=z_2\\
x_3(a_1+\cdots+a_3)+y_3(a_3+\cdots+a_n)=z_3\\
\cdots\\
x_n(a_1+a_2+\cdots+a_n)+y_n(a_n)=z_n\\
\end{array}
\right.
$$
对于这个方程组，我们可以把每个方程进行整理，转化为这样的形式：
\left\{
\begin{array}{}
c_{1,1}a_1+c_{1,2}a_2+\cdots+c_{1,n}a_n=z_1\\
c_{2,1}a_1+c_{2,2}a_2+\cdots+c_{2,n}a_n=z_2\\
\cdots\\
c_{n,1}a_1+c_{n,2}a_2+\cdots+c_{n,n}a_n=z_n
\end{array}
\right.
$$
也就是把每个方程中，未知数的系数求出来。
之后使用高斯消元直接解方程。
过程中，若存在自由元，则为解的个数为 $10^9+7$，不管有几个自由元都是。不知道为什么。
若方程组通过化简可以得到 $0\cdot x=0$，那么 $x$ 的取值任意，称 $x$ 为自由元。
时间复杂度 $\mathcal{O}(n^3)$.
$\rm{Subtask}$ $4$
对于另外 $22\%$ 的数据，保证有唯一解。
题目中的方程显然不同于随机生成的方程，要找到一些可以利用的特性。
有可能可以发现，方程与区间和密切相关，于是考虑前缀和。
设 $s_i=\sum_{j=1}^ja_j$，则方程组通项为：
x_i\cdot s_i+y_i(s_n-s_{j-1})=z_i\quad (i)
$$
也就是：
-y_i\cdot s_{j-1} + x_i\cdot s_i+y_i\cdot s_n=z_i\quad (i)
$$
这种形式下，每个方程涉及的未知数更少，更容易处理。
考虑系数矩阵的形态：
\begin{matrix}
&&\textcolor{gray}{1} &\textcolor{gray}{2} &\textcolor{gray}{3} &\textcolor{gray}{4} &\textcolor{gray}{5} &\textcolor{gray}{6}\\\\
\textcolor{gray}{1} &&x & & & & &x \\
\textcolor{gray}{2} &&x &x & & & &x \\
\textcolor{gray}{3} && &x &x & & &x \\
\textcolor{gray}{4} && & &x &x & &x \\
\textcolor{gray}{5} && & & &x &x &x \\
\textcolor{gray}{6} && & & & &x &x \\
\end{matrix}
$$
$x$ 表示系数不为 $0$。
这样第 $1$ 行只需要消第 $2$ 行，第 $2$ 行消第 $3$ 行，以此类推，最后的矩阵形如：
\begin{matrix}
&&\textcolor{gray}{1} &\textcolor{gray}{2} &\textcolor{gray}{3} &\textcolor{gray}{4} &\textcolor{gray}{5} &\textcolor{gray}{6}\\\\
\textcolor{gray}{1} &&x & & & & &x \\
\textcolor{gray}{2} &&0 &x & & & &x \\
\textcolor{gray}{3} && &0 &x & & &x \\
\textcolor{gray}{4} && & &0 &x & &x \\
\textcolor{gray}{5} && & & &0 &x &x \\
\textcolor{gray}{6} && & & & &0 &x \\
\end{matrix}
$$
于是 $a_n$ 可求，分别代入第 $1\sim n-1$ 个方程即可求解。
这样的时间复杂度是 $\mathcal{O}(n\log n)$，$\log n$ 来自求逆元。
对于空间，每行只有 $3$ 个系数需要存，不用开矩阵，也是 $\mathcal{O}(n)$ 的。
$\rm{Subtask}$ $5$
对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\leq x_i, y_i\leq 10^9+7$，$0\leq z_i\leq 10^9+7$.
上面的时空复杂度已经可以通过此题，只需要多加一个判断解的个数。
判断的方法在 $\rm{Subtask}$ $1$ 中提到过了，但需要另外注意：
存在一个自由元，其值可以任取，不代表方程组有无穷组解。只要有一个变量是无解的，则方程组无解。
代码
删去了 read() 和头文件。
#define int long long
const int MAXN = 2e5 + 10, mod = 1e9 + 7;
inline int power(int x, int k) {
int ret = 1;
while(k) {
if(k & 1) ret = ret * x % mod;
x = x * x % mod;
k >>= 1;
}
return ret;
}
inline int inv(int x) {return power(x, mod - 2);}
int T, n;
int x[MAXN], y[MAXN], z[MAXN];
int a[MAXN], b[MAXN], c[MAXN];
int s[MAXN];
signed main() {
T = read();
while(T--) {
n = read();
for(int i = 1; i <= n; i++) {
x[i] = read(); y[i] = read(); z[i] = read();
}
//对每个x,y,z，x[i]s[i] - y[i]s[i-1] + y[i]s[n] = z[i]
for(int i = 1; i < n; i++) {//高斯消元解前缀和
a[i] = mod - y[i]; b[i] = x[i]; c[i] = y[i];
} a[n] = mod - y[n]; c[n] = (x[n] + y[n]) % mod;
for(int i = 1; i < n; i++) {//用第i行消掉第i+1行的第i列
int k = a[i + 1] * inv(b[i]) % mod;
(a[i + 1] -= k * b[i] % mod) %= mod;
(c[i + 1] -= k * c[i] % mod) %= mod;
(z[i + 1] -= k * z[i] % mod) %= mod;
}
int roots = 1;
if(c[n] == 0 && z[n] != 0) {
putchar('0'); putchar('\n');
continue;
}
else if(c[n] == 0 && z[n] == 0) roots = mod;
else s[n] = z[n] * inv(c[n]) % mod;
for(int i = 1; i <= n - 1; i++) {
int right = (z[i] - c[i] * s[n] % mod) % mod;
if(b[i] == 0 && right != 0) {roots = 0; break;}
else if(b[i] == 0 && right == 0) roots += mod;
else s[i] = ((z[i] - c[i] * s[n] % mod) * inv(b[i]) % mod + mod) % mod;
}
if(roots != 1) {printf("%lld\n", roots); continue;}
else {putchar('1'); putchar('\n');}
for(int i = 1; i <= n; i++)
printf("%lld ", ((s[i] - s[i - 1]) % mod + mod) % mod);
putchar('\n');
}
return 0;
}