牛客寒假算法基础集训营1D-点一成零 题解

题目大意

给你一个01矩阵，每次操作可以点击一个写着1的格子，将这个格子所在的1连通块全部变成0。

有k次永久修改，将一个格子变成1，求每次修改之后有多少种不同的方案，可以把全部格子的1都变成0？

解题思路

说实话，我都不知道并查集可以这么用。

首先要知道没有修改情况的答案是多少。

对于每个连通块，存在着$x!$种选择情况。

对于每个连通块内部，存在着$size[i]$种选择情况。

所以答案为$x!\times size[i]$。

对于修改之后。

先假设增加了一个连通块，cnt++。

然后遍历这个点的上下左右。

如果周围存在相邻的联通块，直接合并。

合并的时候，$\Large ans = \frac{ans\times (size[a]+size[b])}{cnt\times size[a]\times size[b]}$。

同时需要cnt–，注意使用逆元。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 5e5, maxn = 550, mod = 1e9 + 7;
int father[N], siz[N];
char Map[maxn][maxn];
int dx[] = { 0,1,0,-1 }, dy[] = { -1,0,1,0 };

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b, ll mod) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans = (ans * a) % mod;
		a = (a * a) % mod, b >>= 1;
	}
	return ans % mod;
}

int find(int x) {
	return father[x] == x ? x : father[x] = find(father[x]);
}

void join(int rt1, int rt2) {
	int fa1 = find(rt1), fa2 = find(rt2);
	if (fa1 != fa2)	siz[fa1] += siz[fa2], father[fa2] = fa1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	ll n; cin >> n;
	rep(i, 0, (n + 1) * (n + 1))	father[i] = i, siz[i] = 1;
	rep(i, 1, n) {
		rep(j, 1, n)	cin >> Map[i][j];
	}
	rep(i, 1, n) {
		rep(j, 1, n) {
			rep(k, 0, 3) {
				int tx = j + dx[k], ty = i + dy[k];
				if (Map[i][j] == '1' && Map[ty][tx] == '1')	join(i * n + j, ty * n + tx);
			}
		}
	}
	int cnt = 0;
	ll ans = 1;
	rep(i, 1, n) {
		rep(j, 1, n)	if (Map[i][j] == '1' && father[i * n + j] == i * n + j)	cnt++, ans = (ans * siz[i * n + j]) % mod;
	}
	rep(i, 1, cnt)	ans = (ans * i) % mod;
	int k; cin >> k;
	while (k--) {
		int x, y; cin >> y >> x;
		x++, y++;
		if (Map[y][x] == '1') {
			cout << ans << endl;
			continue;
		}
		Map[y][x] = '1';
		cnt++;
		ans = (ans * cnt) % mod;
		rep(i, 0, 3) {
			int tx = x + dx[i], ty = y + dy[i];
			int rt1 = find(y * n + x), rt2 = find(ty * n + tx);
			if (Map[ty][tx] == '1' && rt1 != rt2) {
				ans = (ans * qpow(cnt, mod - 2, mod)) % mod;
				ans = (ans * qpow(siz[rt1], mod - 2, mod)) % mod;
				ans = (ans * qpow(siz[rt2], mod - 2, mod)) % mod;
				ans = (ans * (siz[rt1] + siz[rt2])) % mod;
				cnt--;
				join(rt1, rt2);
			}
		}
		cout << ans << endl;
	}
	return 0;
}