[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)\)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const ll INF = 9e18;
ll m, best = INF;
vector<ll> 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[i] > remain) continue;      // 剪枝：因子太大if (remain % fib[i] == 0) {         // 可整除，尝试使用该因子dfs(remain / fib[i], total_len + i + 1, i);}}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> m;// 特判 m = 1if (m == 1) {cout << "1\n";return 0;}// 生成斐波那契数列fib.push_back(1);fib.push_back(1);while (fib.back() <= m) {int s = fib.size();fib.push_back(fib[s-1] + fib[s-2]);}// 从不超过 m 的最大斐波那契数开始搜索int start = lower_bound(fib.begin(), fib.end(), m) - fib.begin();if (fib[start] > m) start--;dfs(m, 0, start);// 输出结果if (best == INF) {cout << "NIE\n";} else {cout << best << "\n";}return 0;
}