2021-2022 ACM-ICPC Brazil Subregional Programming Contest G.Getting in Shape 构造+思维+搜索

Problem Analysis

题目大意：做练习，一共有两种练习 A B AB AB：

• 做完一个练习 B B B之后可以进入下一个练习；
• 完成一个练习 A A A之后可以进入下一个练习或者跳过下一个练习进入后一个练习。

对于某个给定的练习序列 s s s，可能存在多种完成方式。现在给定某个序列的的完成方式数目，要求求一个满足要求的序列，使能该序列的完成方式数目符合要求。该序列必须以 B B B结尾，且要求答案保证输出的方案是字典序最小的序列。

题目分析：

首先考虑连续的 A A A序列 + + +一个 B B B，很容易发现每增加一个 A A A，序列的完成的种数一直呈斐波那契数列增长。即每增加一个 A A A，前两次都会对总种数产生贡献。由于一个 B B B的分隔，可以使几段 A . . . B A...B A...B的贡献相互独立。所以对于给定的方案数，可以使用几个斐波那契数列项相乘得到，也就是说可以用几个 A . . . B A...B A...B序列构成。

那么对于每个给定的方案数目，我们只需要对其因子进行枚举，看是否为斐波那契数即可。同时为了保证字典序最大，我们应该从大因子开始枚举，枚举到合法的立即终止返回。

#include 
#define int long long
using namespace std;

const int N = 100;
int fib[N] = {1, 1}, ans[N], ok = 0;

inline void dfs(int num, int cnt, int now){
    if(num == 1){
        ok = 1;
        for(int i = 1; i > n;
    if(n == 1) return cout