RikkawithGame

NC213947. RikkawithGame

描述

Rikka and her classmates are playing an online game. There are n players in the game, and there are some pairs of friend relationships among players. The friend relationship is bidirectional.
At the beginning of the game, one player is selected as dragon randomly, and other players are marked as hero.
The game proceeds in turns. Each turn contains the following three steps:

Each hero is asked to decide whether to attack the dragon. Note that for each player, others' decisions are unknown when making this decision. If a hero is a friend of the dragon, then this hero must choose not to attack;
If all the heroes choose not to attack the dragon, the game ends immediately. Otherwise, the dragon is eliminated by heroes;
Suppose player i is the first hero (the player with the smallest index) who chooses to attack. Player i becomes a new dragon and then a new turn starts.

When the game ends, each alive hero will gain 10 points, the last dragon will get 100 points and each eliminated player will gain only 1 point.
All players want to maximize his/her points, and suppose all players are clever enough.
For each player, Rikka wants you to determine: If this player is selected as the dragon at the beginning, whether the game will end immediately in the first turn?

输入描述

The first line contains a single integer , representing the number of players.
Then n lines follow. Each line contains an 01-string  of length n.  if and only if player i and player j are friends.
The input guarantees that  and .

输出描述

Output a single line with a 01-string res of length n. $res_i = 1$ if and only if the game will end immediately in the first turn if player i is selected as the first dragon.

示例1

输入:

2
00
00

输出:

说明:

Whatever which player is selected, the other player will choose to attack: He/she will get 100 points if he chooses to attack, otherwise, he/she can get only 10 points. Therefore, the game continues to the second turn.

示例2

输入:

输出:

说明:

Without loss of the generality, suppose the third player is selected as the first dragon. Then:
1. For the first player, if he/she chooses to attack, he/she will become the dragon of the second turn. However, according to the first sample, he/she will then be eliminated and will get only 1 point. Therefore, he/she will choose not to attack and thus he/she can get 10 points.
2. For the second player, for the same reason, he/she will choose not to attack, too.
Therefore, the game will end in the first turn.

示例3

输入:

输出:

示例4

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 185ms, 内存消耗: 2680K, 提交时间: 2021-01-18 23:39:51

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const int mod = 998244353;
inline int qp(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
		b >>= 1;
	}
	return res;
}
mt19937 rng(1145141);
int n, a[N][N * 2], cnt;
char str[N];
inline void Gauss() {
	for (int i = 1, j, k; i <= n; i++) {
		for (j = cnt + 1; j <= n; j++) if (a[j][i]) break;
		if (j > n) continue;
		cnt++;
		if (j != cnt) for (k = 1; k <= n * 2; k++) swap(a[j][k], a[cnt][k]);
		int iv = qp(a[cnt][i], mod - 2);
		for (j = cnt + 1; j <= n; j++) {
			int t = 1ll * (mod - a[j][i]) * iv % mod;
			for (k = i; k <= n * 2; k++) a[j][k] = (a[j][k] + 1ll * a[cnt][k] * t) % mod;
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf(" %s", str + 1);
		for (int j = i + 1; j <= n; j++) {
			if (str[j] == '0') {
				int x = uniform_int_distribution<int>(1, mod - 1)(rng);
				a[i][j] = x;
				a[j][i] = mod - x;
			}
		}
	}
	for (int i = 1; i <= n; i++) a[i][i + n] = uniform_int_distribution<int>(1, mod - 1)(rng);
	Gauss();
	for (int s = 1; s <= n; s++) {
		int flag = 0;
		for (int i = cnt + 1; i <= n; i++) if (a[i][n + s]) { flag = 1; break; }
		putchar(flag ? '1' : '0');
	}
	putchar('\n');
	return 0;
}