[POI 2021/2022 R1] Domino 题解

[POI 2021/2022 R1] Domino 题解

P9416 题目导航
问题分析

(虽然但是题目说的已经很清楚了，但我还是想让大家听得跟明白一点，绝对不是在水字数显得我写的很多)
给定一个 \(2 \times n\) 的网格，我们需要用 \(1 \times 2\) 或 \(2 \times 1\) 的骨牌覆盖所有未被占用的格子。要求找到最小的 \(n\)，使得存在一种占用格子的设置方式，使得覆盖方案数恰好为 \(m\)。无解输出 NIE。
核心思路

1. 无占用格子的覆盖方案数

对于一个 \(2 \times n\) 的完整网格，覆盖方案数满足斐波那契关系：

• \(f(0) = 1\)（大概就是空棋盘嗯对）
  
• \(f(1) = 1\)（只能竖放一个 \(2 \times 1\) 的骨牌）
  
• \(f(n) = f(n-1) + f(n-2)\)（第一列竖放，或者前两列横放两个 \(1 \times 2\) 骨牌，就是递推公式）
  

2. 利用占用格子分割网格

我们可以用完全被占用的列将网格分割成多个独立段，每段内部没有占用格子：

• 总方案数 \(m\) 等于各段方案数的乘积
  
• 设第 \(i\) 段长度为 \(a_i\)（即 \(2 \times a_i\) 网格），则段方案数为 \(f(a_i)\)
  
• 段间需要分隔列，总列数 \(n = \sum a_i + (k-1)\)，其中 \(k\) 为段数
  

3. 问题转化

我们需要将 \(m\) 分解为斐波那契数的乘积：\(m = \prod f(a_i)\)，并最小化 \(n = \sum a_i + (k-1)\)。
注意：

• \(f(1) = 1\) 不改变乘积但增加长度，因此不考虑 \(a_i = 1\) 的段
  
• 当 \(m = 1\) 时，可直接用一列全部占用的格子实现，\(n = 1\)
  

4. 搜索算法

由于斐波那契数增长迅速，\(m \le 10^{18}\) 时涉及的项数不多。所以我们直接通过 DFS 搜索分解方案：

• 预处理斐波那契数列
  
• 从大到小枚举斐波那契数作为因子
  
• 记录当前总长度，超过已知最优解时剪枝
  
• 找到分解方案后计算 \(n = \text{总长度} - 1\)（减去最后一个分隔列）
  

完啦！！耶！！！
算法分析

时间复杂度

• 斐波那契数列在 \(10^{18}\) 内约 90 项
  
• DFS 搜索的分支有限，剪枝有效
  
• 实际运行效率很高
  

空间复杂度

• 存储斐波那契数列：\(O(\log m)\)
  
• 递归深度：\(O(\log m)\)
  

[code]#include using namespace std;using ll = long long;const ll INF = 9e18;ll m, best = INF;vector fib;// 搜索将剩余值分解为斐波那契数乘积的最小长度void dfs(ll remain, ll total_len, int last_idx) {    if (remain == 1) {                      // 成功分解        best = min(best, max(total_len - 1, 0LL));        return;    }    if (total_len >= best) return;          // 剪枝：当前长度已不够优        // 从大到小枚举可能的斐波那契因子    for (int i = last_idx; i >= 2; i--) {        if (fib > remain) continue;      // 剪枝：因子太大        if (remain % fib == 0) {         // 可整除，尝试使用该因子            dfs(remain / fib, total_len + i + 1, i);        }    }}int main() {    ios::sync_with_stdio(false);    cin.tie(0);        cin >> m;        // 特判 m = 1    if (m == 1) {        cout