【洛谷-P7887】「MCOI-06」Existence of Truth

题目来源#

【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$ 满足：

先求满足条件的解的个数。若只有一组解，求出 $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$ 的方程：

即：

注意到此时 $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$ 组解。

三、 对于其他情况均有唯一解：

用乘法逆元处理即可。

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$ 个方程列出：

若 $x_i=y_i=1$，那么：

容易想到把 $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$。

对于这个方程组，我们可以把每个方程进行整理，转化为这样的形式：

也就是把每个方程中，未知数的系数求出来。

之后使用高斯消元 ↗直接解方程。

过程中，若存在自由元，则为解的个数为 $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$ 表示系数不为 $0$。

这样第 $1$ 行只需要消第 $2$ 行，第 $2$ 行消第 $3$ 行，以此类推，最后的矩阵形如：

于是 $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;
}