题解：笛卡尔征服 - 矩形区域划分

算法思路

本题要求计算在 $N \times M$ 的矩形中，用 $2:1$ 的矩形（可横放或竖放）进行划分时，所需的最小和最大块数。这是一个基于记忆化搜索的分治策略问题。

1. 问题分析

每个区域必须满足：

• 形状为矩形
• 长边长度 = 2 × 短边长度
• 边长为整数

目标：找到所有可能划分中区域数量的最小值和最大值。

2. 关键观察

• 对称性：可以假设 $x \ge y$（长边为 $x$，短边为 $y$）
• 基本情况：
  • 如果 $y = 0$：无法划分，返回 $(0, 0)$
  • 如果 $x = 2y$ 且 $y$ 为奇数：只能放一个 $2:1$ 矩形，返回 $(1, 1)$
• 递归关系：通过不同的切割方式递归求解子问题

3. 主要切割策略

策略1：沿长边切割

当 $x > 2y$ 时：

• 如果 $y$ 为奇数：可以切出若干个 $2y \times y$ 的矩形
• 如果 $x \ge 4y$：考虑不同的切割倍数

策略2：沿短边切割

当无法直接切出完整矩形时：

• 从长边或短边切掉一部分，递归处理剩余部分

代码实现

#include <bits/extc++.h>
using namespace std;

// 哈希函数用于pair
static inline unsigned int shift(unsigned int x) {
    return ((x ^= x << 13) ^= x >> 17) ^= x << 5;
}

template<>
struct tr1::hash<pair<unsigned int, unsigned int>> {
    size_t operator()(pair<unsigned int, unsigned int> x) const {
        return shift(shift(x.first) + x.second);
    }
};

// 记忆化存储
__gnu_pbds::gp_hash_table<pair<unsigned int, unsigned int>, 
                         pair<unsigned int, unsigned int>> store;

#define qwq(__X, __Y) return store[{__X, __Y}] =

// 记忆化搜索函数
pair<unsigned int, unsigned int> dfs(unsigned int x, unsigned int y) {
    // 确保 x >= y
    if (x < y) swap(x, y);
    
    // 基本情况
    if (y == 0) return {0, 0};
    if (x == (y << 1) && (y & 1)) return {1, 1};
    if (x == y) return {2, 1 + dfs(x, x >> 1).second};
    
    // 检查记忆化结果
    auto it = store.find({x, y});
    if (it != store.end()) return it->second;
    
    // 策略1：长边远大于短边
    if (x > (y << 1)) {
        // 情况1.1：y为奇数，可以切出完整矩形
        if (y & 1) {
            unsigned int w = x / (y << 1);
            auto inner = dfs(x - w * (y << 1), y);
            qwq(x, y) { inner.first + w, inner.second + w };
        }
        
        // 情况1.2：可以切出多个矩形
        if (x >= (y << 2)) {
            unsigned int w = x / (y >> 1);
            unsigned int a = (w >> 2) - 1;
            unsigned int b = w - 3;
            auto ia = dfs(x - a * (y << 1), y);
            auto ib = dfs(x - b * (y >> 1), y);
            qwq(x, y) { 
                min(ia.first + a, ib.first + b), 
                ib.second + b 
            };
        }
        
        // 情况1.3：一般情况
        unsigned int w = (x - y - (y >> 1)) / (y >> 1);
        auto ia = dfs(x - (y << 1), y);
        auto ib = dfs(x - w * (y >> 1), y);
        qwq(x, y) { 
            min(ia.first + 1, ib.first + w), 
            ib.second + w 
        };
    }
    
    // 策略2：从长边切割
    if (x & 1) {
        auto inner = dfs(y, x - (y >> 1));
        qwq(x, y) { inner.first + 1, inner.second + 1 };
    }
    
    // 策略3：从短边切割
    if (y & 1) {
        auto inner = dfs(x, y - (x >> 1));
        qwq(x, y) { inner.first + 1, inner.second + 1 };
    }
    
    // 策略4：综合两种切割方式
    auto ia = dfs(y, x - (y >> 1));
    auto ib = dfs(x, y - (x >> 1));
    qwq(x, y) { 
        min(ia.first, ib.first) + 1, 
        max(ia.second, ib.second) + 1 
    };
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    unsigned int n, m;
    cin >> n >> m;
    
    auto ans = dfs(n, m);
    cout << ans.first << ' ' << ans.second;
    
    return 0;
}

关键优化

1. 记忆化搜索

• 使用哈希表存储已计算的结果
• 避免重复计算相同子问题

2. 哈希函数优化

• 自定义高效的哈希函数处理 pair<unsigned int, unsigned int>
• 使用 gp_hash_table 获得更好的性能

3. 分治策略

• 将大矩形分解为小矩形
• 分别计算最小和最大值

复杂度分析

• 时间复杂度：$O(\text{状态数})$，由于记忆化，每个状态只计算一次
• 空间复杂度：$O(\text{状态数})$，用于存储记忆化结果

对于 $N, M \leq 10^8$ 的数据规模，通过合理的状态划分，算法能够在可接受的时间内运行。

算法正确性

1. 完备性：考虑了所有可能的切割方式
2. 最优性：通过比较不同切割策略得到最小和最大值
3. 终止性：矩形尺寸在递归中不断减小，最终到达基本情况

该算法通过分治+记忆化的方法，高效地解决了大规模矩形划分的计数问题。