跳转至

251023 模拟赛

T4

给你一个 \(n\times n\) 的正整数矩阵，维护三种操作：

  • 将一条平行于主对交线的直线（截距为整数）上的数字全部 \(rev\)；
  • 将一条平行于副对角线的直线（同上）上的数字全部 \(rev\)；
  • 查询全局 \(\gcd\)；

\(rev\) 表示将一个数字在十进制下高低位翻转（即 \(12345\to 54321\)）。

\(n\le 1000,~q\le 10^6,~a_i\le 10^9,~a_i\bmod 10\ne 0\)

作线性变换 \((i,j)\to (i+j-1,i+j-n)\)，修改变为对行和列修改。

高低位翻转和 \(\gcd\) 似乎没有什么很好的性质。考虑 \(\gcd\) 的一些经典做法：将不同质因子分开做。此处注意到一个关键性质：任选矩阵中的一个数字 \(x\)，那么 \(\gcd|~x\vee \gcd|~rev(x)\)。因此只需考虑 \(x\) 和 \(rev(x)\) 的质因子即可。

考虑对于一个质因子 \(p^k\) 怎么做，我们需要对每个时刻维护出 \(p^k\) 是否整除所有数字。发现每个点只有两个取值。对于一个点 \(x=a_{i,j}\)，如果 \(x\) 和 \(rev(x)\) 都是 \(p^k\) 的倍数，那么无需考虑；如果都不整除，那么永远都不合法；如果 \(p^k\) 整除 \(x\) 但不整除 \(rev(x)\)，那么要求第 \(i\) 行和第 \(j\) 列的翻转状态相同；另一种情况则反之，要求不相同。

考虑建图，用 \(2\)-染色 刻画。给每一行和每一列建一个虚点，矩阵中一个点对应一条边权为 \(0/1\) 的边。图会形成若干连通块，对每个连通块分别 \(2\)-染色。当行和列的翻转状态和连通块的染色状态完全相同或相反时合法。对每个连通块两种情况分别记录匹配的点的数量，如果等于连通块 \(sz\) 就给 \(cur\) 加一，当 \(cur\) 等于连通块数量时合法。显然容易支持单点 filp。

先把 \(a_{1,n}\)（对应原图左上角）和 \(rev(a_{1,n})\) 的质因子筛出来并去重，然后对每个质因子从小大枚举指数，将 \(p^m\) 的贡献拆到 \(k=1,2,3\cdots m\) 上，这样实现比较简单。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 2010;
const int M = 1e6 + 10;
const int V = 1e5 + 10;

struct Edge {
    int v, w;
};

inline int rev(int x) {
    int res = 0;
    while(x) res = res * 10 + x % 10, x /= 10;
    return res;
}

struct Op {
    int tp, v;
} op[M];

int n, q;
int a[N][N], ans[M];
int col[2 * N], side[2 * N], sz[2 * N], nn;
vector<Edge> adj[2 * N];

int npri[V], pri[V], pcnt;

void dfs(int u) {
    col[u] = nn;
    sz[nn]++;
    for(Edge e : adj[u]) {
        int v = e.v, w = e.w;
        if(col[v] && (side[u] ^ side[v]) != w) throw;
        if(col[v]) continue;
        side[v] = side[u] ^ w;
        dfs(v);
    }
}

int match[2 * N][2], sta[2 * N];
bool check(int x, int v) {
    nn = 0;
    for(int i = 1; i <= 4 * n; i++) {
        adj[i].clear();
        col[i] = side[i] = sz[i] = 0;
        match[i][0] = match[i][1] = 0;
        sta[i] = 0;
    }
    for(int i = 1; i <= 2 * n; i++) {
        for(int j = 1; j <= 2 * n; j++) {
            if(a[i][j] == 0) continue;
            bool o0 = (a[i][j] % x == 0);
            bool o1 = (rev(a[i][j]) % x == 0);
            if(!o0 && !o1) return false;
            if(o0 && o1) continue;
            adj[i].push_back({j + 2 * n, o1});
            adj[j + 2 * n].push_back({i, o1});
        }
    }
    try {
        for(int i = 1; i <= 4 * n; i++) {
            if(!col[i]) { ++nn; dfs(i); }
        }
    } catch(...) {
        return false;
    }
    int cur = 0; bool flag = false;
    for(int i = 1; i <= 4 * n; i++) {
        match[col[i]][side[i]]++;
        if(match[col[i]][side[i]] == sz[col[i]]) ++cur;
    }
    for(int i = 1; i <= q; i++) {
        int x = op[i].v;
        if(op[i].tp) {
            if(match[col[x]][sta[x] ^ side[x]] == sz[col[x]]) --cur;
            match[col[x]][sta[x] ^ side[x]]--;
            sta[x] ^= 1;
            match[col[x]][sta[x] ^ side[x]]++;
            if(match[col[x]][sta[x] ^ side[x]] == sz[col[x]]) ++cur;
        } else {
            x += 2 * n;
            if(match[col[x]][sta[x] ^ side[x]] == sz[col[x]]) --cur;
            match[col[x]][sta[x] ^ side[x]]--;
            sta[x] ^= 1;
            match[col[x]][sta[x] ^ side[x]]++;
            if(match[col[x]][sta[x] ^ side[x]] == sz[col[x]]) ++cur;
        }
        if(cur == nn) ans[i] *= v, flag = true;
    }
    return flag;
}

int main() {

    freopen("gcd.in", "r", stdin);
    freopen("gcd.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int i = 2; i < V; i++) {
        if(!npri[i]) pri[++pcnt] = i;
        for(int j = 1; j <= pcnt; j++) {
            if(i * pri[j] >= V) break;
            npri[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> a[i + j - 1][i - j + n];
        }
    }
    for(int i = 1; i <= q; i++) {
        char c; int v;
        cin >> c >> v;
        op[i].tp = (c == '+');
        op[i].v = v;
        if(op[i].tp) op[i].v -= 1;
        else op[i].v += n;
    }

    vector<int> fac;
    for(int i = 1, x = a[1][n]; i <= pcnt; i++) {
        if(x % pri[i] == 0) fac.push_back(pri[i]);
        while(x % pri[i] == 0) x /= pri[i];
    }
    for(int i = 1, x = rev(a[1][n]); i <= pcnt; i++) {
        if(x % pri[i] == 0) fac.push_back(pri[i]);
        while(x % pri[i] == 0) x /= pri[i];
    }
    sort(fac.begin(), fac.end());
    fac.resize(unique(fac.begin(), fac.end()) - fac.begin());

    for(int i = 1; i <= q; i++) ans[i] = 1;
    for(int i : fac) {
        int j = i;
        while(check(j, i)) j *= i;
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << '\n';

    return 0;
}