自动搬运

查看原文

来自洛谷，原作者为

	bh2013 我是个『蒟蒻』！QAQฏ๎็็็็็็ด้้้้้็็็็็ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็

搬运于2025-08-24 22:48:10，当前版本为作者最后更新于2025-08-06 17:25:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

1. 题目大意：

已经很清楚了，无需赘述

2. 解法：

先考虑如果给一个 $n$，没有占用的格子，让我们求 $m$，正是斐波那契数列，那么我们的答案矩形，是不是可以由若干个这样的矩形拼接而成，在每两个矩形中间加上被占用的格子，用来划分。再根据乘法原理，可知，答案矩形的方案数 $m$，是由所有小矩阵的方案数相乘得来的，所以这个问题就转化成了，对于一个数，将其拆分成斐波那契数列中的若干项相乘。同时记录最小长度即可。注意特判 $m=1$ 的情况。

3. code：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int m, ans = 9e18;
vector <int> fib;

void dfs(int shengyu, int len, int nxt) { // 当 m 还剩下的数为 shengyu，已经"拆出"了 len 个数了，上一个拆分数为 nxt
	if (shengyu == 1) {
		ans = min(ans, max(len - 1, 0ll));
		return ;
	}
	if (len >= ans) return ;
	for (int i = nxt; i >= 2; i --) {
		if (shengyu % fib[i] == 0) {
			dfs(shengyu / fib[i], len + i + 1, i);
		}
	}
	return ;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> m;
	if (m == 1) {
		cout << 1 << '\n';
		return 0;
	}
	fib.emplace_back(1);
	fib.emplace_back(1);
	while (fib[fib.size() - 1] <= m) fib.emplace_back(fib[fib.size() - 1] + fib[fib.size() - 2]); // 预处理出斐波那契数列
	dfs(m, 0, (int)(lower_bound(fib.begin(), fib.end(), m) - fib.begin()));
	if (ans == 9e18) cout << "NIE" << '\n'; // 无解
	else cout << ans << '\n'; // 有解
	return 0;
}

给我这只蒟蒻点一个赞吧