https://codeforces.com/contest/1107/problem/D
题目大意
给出一个 $n \times n$ 的 $01$ 矩阵 $A$。规定 $B$ 为 $A$ 的一个 $x$ 压缩矩阵，如果 $x | n$ 以及 $A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]$（$1$-indexed）。
$4 \le n \le 5200$，且 $4 | n$。
$A$ 按照每行每 $4$ 位压缩成一个十六进制数的方式，给出这个十六进制数串（$0 \sim F$）。
简要题解
题目是 $1$ 开始的下标，如果是 $0$ 开始的下标，则我们应该把除法都替换为向下取整。以下均以向下取整讨论（形式简单一些）。
显然对于某个 $x$ 我们可以 $n ^ 2$ 的检查。但是如果只考虑能整除 $n$ 的 $x$ 则这样的 $x$ 有 $O(\sqrt n)$ 个，实际上并不能通过本题。比如 $5200 = 2^4 \times 5^2 \times 13$ 一共有 $5 \times 3 \times 2 = 30$ 个约数要判断。
void solve() {
int n; cin >> n;
string s;
for (int i = 0; i < n; i++) {
cin >> s;
for (int j = 0, k = 0; k < n; j++, k += 4) {
int dec = hex2dec[s[j]];
for (int l = 0; l < 4; l++) {
a[i][k + l] = ((dec >> l) & 1);
}
}
}
auto check = [&](int x) -> bool {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] != a[i / x * x][j / x * x]) {
return false;
}
}
}
return true;
};
int ans = 1;
vector<int> valid(n + 1, 1);
for (int i = 2; i <= n; i++) {
if ((n % i) || !valid[i]) continue;
if (!check(i)) {
for (int j = i; j <= n; j += i) {
valid[j] = 0;
}
} else {
cmax(ans, i);
}
}
cout << ans << '\n';
}
实际上我们并不需要判断所有的因子。注意到如果对于 $gcd(x, y) = 1$ 如果 $x$ 是合法压缩，$y$ 是合法压缩，则 $xy$ 是合法压缩。
也就是要证明 $a[xy * k + i][xy * l + j]$ = $a[xy * k][xy * l], \forall 0 \le k, l < \frac{n}{xy}, 0 \le i, j < xy$。
注意到两维其实是可以分开的。不妨先证明对于
$a[x * j + i] = a[x * j], \forall 0 \le j < \frac{n}{x}, 1 \le i < x$ 和 $a[y * j + i], \forall 0 \le j < \frac{n}{y}, 1 \le i < y$，则 $a[xy * j + i] = a[xy * j], \forall 0 \le j < \frac{n}{xy}, 1 \le i < xy$。
我们从另一个角度考虑，这相当于对于 $x$ 只有 $i = x, 2x, 3x$ 的位置允许 $a[i] \neq a[i - 1]$。而 $y$ 只允许 $i = y, 2y, 3y$ 的位置 $a[i] \neq a[i - 1]$。由 $gcd(x, y) = 1$ 则只有 $i = k \cdot lcm(x, y) = kxy$ 的下标可能满足 $a[i] \neq a[i - 1]$ 即其满足 $xy$ 压缩。
这样我们只需判断 $n$ 的因子及其各个幂次，然后再合并即可，我们就得到了一个 $O(n ^ 2 \log n)$ 的做法。注意到质因子最多有 $12$ 个因此最多是 $12$ 次大概是刚才做法的 $1 / 3$。
坑点：
这题样例几乎等于没有。为了读入所以输入变成了这种形式，但是转化的时候要注意十六进制位与实际位置之间的对应关系（高位实际在左边较小的下标）。
复杂度
$T$：$O(n ^ 2 \log n)$：$812ms$ 时限是 $2.5s$。
$S$：$O(n ^ 2)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
vector<int> isp, pri, minfac, maxfac;
void init_prime(int n) {
isp.assign(n + 1, 1); isp[0] = isp[1] = 0;
minfac.assign(n + 1, 0);
maxfac.assign(n + 1, 0);
for(int i = 2; i <= n; i++) {
if(isp[i]) { pri.push_back(i); isp[i] = pri.size(); minfac[i] = i; }
for(int p : pri) {
if (i > n / p) break;
isp[i * p] = 0;
minfac[i * p] = p;
if(i % p == 0) break;
}
}
for (int i = 2; i <= n; i++) {
maxfac[i] = max(maxfac[i / minfac[i]], minfac[i]);
}
}
vector<int> getfac(int n) {
vector<int> ans;
while (n != 1) {
int v = minfac[n];
ans.push_back(v);
n /= v;
}
return ans;
}
vector<pair<int, int>> getfacpii(int n) {
vector<pair<int, int> > ans;
while (n != 1) {
int v = minfac[n];
if (ans.empty() || ans.back().first != v) {
ans.push_back({v, 1});
} else {
ans.back().second++;
}
n /= v;
}
return ans;
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int M = 5300;
int a[M][M];
map<char, int> hex2dec;
void init() {
for (int i = 0; i < 9; i++) {
hex2dec[i + '0'] = i;
}
for (int i = 0, j = 10; i < 6; i++, j++) {
hex2dec[i + 'A'] = j;
}
init_prime(M);
}
void solve() {
int n; cin >> n;
string s;
for (int i = 0; i < n; i++) {
cin >> s;
for (int j = 0, k = 0; k < n; j++, k += 4) {
int dec = hex2dec[s[j]];
for (int l = 0; l < 4; l++) {
a[i][k + l] = ((dec >> (3 - l)) & 1);
}
}
}
auto check = [&](int x) -> bool {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] != a[i / x * x][j / x * x]) {
return false;
}
}
}
return true;
};
int ans = 1;
auto fac = getfacpii(n);
for (auto [v, c] : fac) {
int cur = 1;
for (int i = 1; i <= c; i++) {
if (check(cur * v)) {
cur *= v;
} else {
break;
}
}
ans *= cur;
}
cout << ans << '\n';
}
int main() {
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
官解做法
因为矩阵里只有 $01$，所以我们可以直接通过求和判断是否全是某种字符。这样再去算所有因子时有
$\sum \frac{n ^ 2}{i ^ 2}$ 而 $\sum \frac{1}{i ^ 2} = \frac{\pi}{6}$ 因此我们得到了一个 $O(n ^ 2)$ 的做法！
Next: [CF] C. Brutality - Educational Codeforces Round 59 (Rated for Div. 2)