【2021寒假集训营第一场】D-点一成零

#include <bits/stdc++.h>
using namespace std;
int n, k;
char a[510][510];
int fa[510*510];
int siz[510*510];
int dir[4][2] = {1,0,-1,0,0,-1,0,1};
const int p = 1e9+7;
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;
}
long long qsm(long long a, long long b)
{
    long long ans = 1, t = a;
    while(b)
    {
        if (b & 1) ans = ans *t % p;
        t = t * t % p;
        b >>= 1;
    }
    return ans % p;
}
long long  ni(int x)
{
    return qsm(x, p-2);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf(" %s", a[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 (a[i][j] =='1')
        {
            if (a[i-1][j] == '1') merge(i*n+j, (i-1)*n+j);
            if (a[i+1][j] == '1') merge(i*n+j, (i+1)*n+j);
            if (a[i][j-1] == '1') merge(i*n+j, i*n+j-1);
            if (a[i][j+1] == '1') merge(i*n+j, i*n+j+1);
        }
    }
    int cnt = 0;
    long long ans = 1;
    for (int i = 1; i <=n; i++)
    for (int j = 1; j <=n; j++)
        if (fa[i*n+j] == i*n+j && a[i][j]  =='1') cnt++, ans = (ans * siz[i*n+j]) % p;

    for (int i = 1; i <= cnt; i++)
        ans = (ans * i) % p;

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

        x++, y++;
        if (a[x][y] == '1')
        {
             printf("%lld\n", ans);
             continue;
        }
        a[x][y] = '1';
        cnt++;
        ans = ans * cnt % p;
        for (int i = 0; i < 4; i++)
        {
            int dx = x+dir[i][0];
            int dy = y+dir[i][1];
            if (a[dx][dy] == '1')
            {
                int f1= find(x*n+y);
                int f2= find(dx*n+dy);
                //cout << ans <<' '<< cnt <<' '<<f1<<':'<<siz[f1]<<' '<<f2<<':'<<siz[f2]<<endl;

                if(f1 != f2)
                {
                   //cout << ni(cnt) <<' '<<ni(siz[f1]) <<' '<<ni(siz[f2])<<endl;
                    ans = ans *ni(cnt) % p;
                    ans = ans *ni(siz[f1]) % p;
                    ans = ans *ni(siz[f2]) % p;
                    ans = ans *(siz[f1]+siz[f2]) % p;
                    cnt--;
                    merge(f1, f2);
                }
            }
        }
        printf("%lld\n", ans);

    }


    return 0;
}