Skip to main content

题解：P9416 [POI2021-2022R1] Domino

· 3 min read
lailai
lailai
Blogger

原题链接​

解题思路​

  1. 使用 1×21\times 2（横向）或 2×12\times 1（纵向）的方块覆盖 2×n2\times n 矩形的所有格子。

  2. 如图，有两种填充方式：使用一个纵向方块或两个横向方块。若某列中，上下两行的填充方式不一致，将导致两侧剩余奇数个格子，无法完全填满。

  1. 这两种填充方式分别覆盖了 11 列和 22 列，如果要覆盖 xx 列，易得方案数为 Fibonacci 数列中第 xx 项 fxf_x。
fn={1n≤1fn−1+fn−2elsef_n=\begin{cases} 1 & n\le1 \\ f_{n-1}+f_{n-2} & \text{else} \end{cases}

  1. 我们可以占用若干列格子（障碍），将整个矩形划分为若干个矩形部分。根据乘法原理，总方案数 mm 等于每部分方案数的乘积。

  2. 为什么 nn 最小时，障碍一定将序列分割成若干部分：如果障碍不分割为若干部分，那么在某个联通部分中必然能找到一对孤立障碍。由于它们外侧格子数量为偶数，因此同一列的另一个格子只能向内侧覆盖，下一列的另一个格子也只能向内侧覆盖……以此类推，两个孤立障碍之间别无选择，等价于直接删除这一段。

  3. 原问题等价为：将正整数 mm 分解为若干个 faif_{a_i} 的乘积，求 n=∑(ai+1)−1n=\sum(a_i+1)-1 的最小值（分割每个部分需要一列障碍，但最后一个不需要）。

  4. 由于 f90>1018f_{90}>10^{18}，可以加上剪枝优化后暴力枚举。

参考代码​

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

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