点一成零

点一成零

首先我们找出再操作之前有多个方案

并查集操作 找出有多少个连通块 然后阶乘再乘上每一个连通块里的点的个数

这里还是好理解的 就假设一个连通块里有8个另一个连通块里有7个 那么我的方案就有可以先点击8个的也可以先点击7个的 这里就是2*1也就是2的阶乘 这个很容易推广理解 然后我在点击8个的时候 可以点击8个里的任意一个 因此 总的方案数就是

2! * 8 * 7

然后我们继续往下操作 这个的难点在于不同情况的处理 可以大致分为三种情况来处理这个修改成1的操作

1，这个本来就是1 ，因此修改它没有意义，直接输出原来的值即可

2，这个点是一个孤立的点 ，因此修改的得到的就是一个新的连通块，所以我们只需要再原来的基础上乘一个k+1(原来有k的连通块)

这里也不难理解 因为就相当于再原来的基础上多了一个只有一个点的连通块

3，这个点是连接了一个或者多个连通块，那么这里就要注意了，我们应该依次处理四个方向，每连接了一个点，我们在2的基础上，就要减少一个连通块，同时除去两个连通块对答案的作用（相当于就是两个连通块合成了一个），然后再乘上一个新的连通块对答案的影响 这里看代码就可以了

然后这里涉及到(a/b)%p这个逆元操作 因为%不能进行分配律，所以要进行逆元操作 具体看代码即可

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll mod = 1e9 + 7;
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }


int n , k;
char mp[510][510];
int fa[510 * 510];
int siz[510 * 510];
int dir[4][2] = {1,0,-1,0,0,-1,0,1};

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

void merge(int x , int y){
    int fx = find(x);
    int fy = find(y);
    if(fx != fy)
        siz[fx] += siz[fy] , fa[fy] = fx;
}

ll ni(int x){
    return qpow(x , mod - 2);
}

int main(void){
    scanf("%d" , &n);
    for(int i = 1 ; i <= n ; ++i){
        scanf(" %s" , mp[i] + 1);
    }
    n++;
    for(int i = 0 ; i <= n * n ; ++i){
        fa[i] = i , siz[i] = 1;
    }
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= n ; ++j){
            if(mp[i][j] == '1'){
                if(mp[i - 1][j] == '1') merge(i * n + j , (i - 1) * n + j);
                if(mp[i + 1][j] == '1') merge(i * n + j , (i + 1) * n + j);
                if(mp[i][j - 1] == '1') merge(i * n + j , i * n + j - 1);
                if(mp[i][j + 1] == '1') merge(i * n + j , i * n + j + 1);
            }
        }
    }
    int cnt = 0;
    ll ans = 1;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= n ; ++j){
            if(fa[i * n + j] == i * n + j && mp[i][j] == '1') cnt++ , ans = (ans * siz[i * n + j]) % mod;
        }
    }

    for(int i = 1 ; i <= cnt ; ++i){
        ans = (ans * i) % mod;
    }

    scanf("%d" , &k);
    while(k--){
        int x , y ;
        scanf("%d%d" , &x , &y);
        x++ , y++;

        if(mp[x][y] == '1'){
            printf("%lld\n" , ans);
            continue;
        }

        mp[x][y] = '1';
        cnt++;
        ans = ans * cnt % mod;
        for(int i = 0 ; i < 4 ; ++i){
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if(mp[dx][dy] == '1'){
                int f1 = find(x * n + y);
                int f2 = find(dx * n + dy);

                if(f1 != f2){
                    ans = ans * ni(cnt) % mod;
                    ans = ans * ni(siz[f1]) % mod;
                    ans = ans * ni(siz[f2]) % mod;
                    ans = ans * (siz[f1] + siz[f2]) % mod;
                    cnt--;
                    merge(f1 , f2);
                }
            }
        }
        printf("%lld\n" , ans);
    }
    return 0;
}

//代码就是看的雨巨巨的 雨巨巨就是讲题的那位大佬