题解：P9416 [POI2021-2022R1] Domino

原题链接

• 洛谷 P9416 [POI2021-2022R1] Domino

解题思路

1. 设 $a_n$ 表示斐波那契数列第 $n+1$ 项数值：

$$a_n=\begin{cases} 1 & n\le1 \\ a_{n-1}+a_{n-2} & \text{else} \end{cases}$$

2. 使用 $1\times 2$（横向）或 $2\times 1$（纵向）的方块来覆盖 $2\times n$ 矩形的所有格子：

• 有两种填充方式，如图所示：

• 如果使用横向方块，则两行必须都是横向方块，否则两侧会有奇数个格子，无法填满。

• 这两种填充方式分别覆盖了 $1$ 列和 $2$ 列，总共要覆盖 $n$ 列，很容易发现方案数是 $a_n$。

3. 我们可以占用 $2\times(k-1)$ 个格子（每两个一组），将整个矩形划分为 $k$ 部分。根据乘法原理，总方案数 $m$ 等于每部分方案数的乘积。

4. 原问题可以等价为：将 $m$ 分解为若干个 $a_i$ 的乘积，每次使用 $a_i$ 的成本是 $i+1$（因为有 $1$ 列格子被占用），我们需要求出最小的成本 $-1$（最后一部分不需要占用格子）。

5. 由于 $a_{90}>10^{18}$，可以采用递归枚举的解决此问题。

参考代码

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

using ll=long long;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=105;
ll a[N]={1,1};
ll ans=inf;
void f(ll x,ll s)
{
	if(x<=1)
	{
		ans=min(ans,s-1);
		return;
	}
	for(int i=2;i<=90;i++)
	{
		if(x%a[i]==0)
		{
			ll u=x,v=s;
			while(u%a[i]==0)
			{
				u/=a[i];
				v+=i+1;
			}
			f(u,v);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for(int i=2;i<=90;i++)
	{
		a[i]=a[i-1]+a[i-2];
	}
	ll m;
	cin>>m;
	f(m,0);
	if(m==1)
	{
		cout<<1<<'\n';
	}
	else if(ans==inf)
	{
		cout<<"NIE"<<'\n';
	}
	else
	{
		cout<<ans<<'\n';
	}
	return 0;
}