自动搬运

查看原文

来自洛谷，原作者为

	lbmzxhb 太菜了，得加训

搬运于2025-08-24 22:56:50，当前版本为作者最后更新于2024-04-06 10:40:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目传送门

思路：

假设第 $i$ 个方碑会被攻击 $x_i$ 次，
且规定攻击第 $i$ 个方碑后会带动第 $j$ 个方碑一起进入下一个状态则 $a_{i,j}$ 为 $1$，不会带动 $a_{i,j}$ 为 $0$，
我们便可以列出以下方程组：

$$\begin{cases} a_{1,1}x_1+a_{2,1}x_2+\cdots+a_{n,1}x_{n}+s_1\equiv t_1&(\operatorname{mod} m)\\ a_{1,2}x_1+a_{2,2}x_2+\cdots+a_{n,2}x_{n}+s_2\equiv t_2&(\operatorname{mod} m)\\ \cdots\\ a_{1,n}x_1+a_{2,n}x_2+\cdots+a_{n,n}x_{n}+s_n\equiv t_n&(\operatorname{mod} m) \end{cases}$$

把左边的 $s_i$ 移项到右边：

$$\begin{cases} a_{1,1}x_1+a_{2,1}x_2+\cdots+a_{n,1}x_{n}\equiv t_1-s_1&(\operatorname{mod} m)\\ a_{1,2}x_1+a_{2,2}x_2+\cdots+a_{n,2}x_{n}\equiv t_2-s_2&(\operatorname{mod} m)\\ \cdots\\ a_{1,n}x_1+a_{2,n}x_2+\cdots+a_{n,n}x_{n}\equiv t_n-s_n&(\operatorname{mod} m) \end{cases}$$

注意到 $a_{i,j},s_{i},t_{i}$ 和 $m$ 题目中已经给出，
于是就可以用高斯消元法解方程了。

注意在输出的时候要 $\operatorname{mod} m$。

Code:

#include <iostream>
#define int long long
using namespace std;
int n, m;
int a[105][105];
inline int upd(int x) {return (x % m + m) % m;}//处理负数
inline int inv(int x) {//保证m为素数，求费马小定理逆元
	int res(1), q(m - 2);
	while (q) {
		if (q & 1) res = res * x % m;
		x = x * x % m;
		q >>= 1;
	}
	return res;
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int k;
		cin >> k;
		a[i][i] = 1;//打自己的时候自己会进入下一个状态
		while (k--) {
			int x;
			cin >> x;
			a[x][i] = 1;
		}
	}
	for (int i = 1; i <= n; i++) cin >> a[i][n + 1];//a[i][n + 1]现在存的是s[i]
	for (int i = 1, x; i <= n; i++) cin >> x, a[i][n + 1] = upd(x - a[i][n + 1]);//a[i][n + 1]现在存的是t[i]-s[i]
	int r(1);
	for (int i = 1; i <= n; i++) {
		int pos(r);
		for (; pos <= n && !a[pos][i]; pos++);
		if (pos == n + 1) continue;//第i个未知数被消完 
		swap(a[r], a[pos]);
		int mul(inv(a[r][i]));
		for (int j = 1; j <= n; j++) {
			if (r != j && a[j][i]) {
				for (int k = n + 1; k >= i; k--) {
					a[j][k] = upd(a[j][k] - a[r][k] * a[j][i] % m * mul % m);
				}
			}
		}
		r++;
	}
	if (r <= n) {
		for (int i = r; i <= n; i++) {//判断无解 
			bool f(0);
			for (int j = 1; j <= n; j++) f |= a[i][j];
			if (!f && a[i][n + 1]) cout << "niuza", exit(0);//0==a且a!=0的情况一定无解 
		}
	}
	r = 1;
	for (int i = 1; i <= n; i++) {
		cout << a[r][n + 1] * inv(a[r][i]) % m << ' ';
		a[r][n + 1] = 0;
		if (!a[r][i + 1]) r++;
	}
}

提交记录
点个赞再走罢

Update:

[2024/4/19] 修改 $\LaTeX$。
[2024/4/20] 题解被hack，修改了代码。