与斐波那契数列相关的对换题目 CF553B Kyoya and Permutation

定义标准循环表示法。
即，对于每个循环，都将其最大值放在最前面，然后将这若干个循环按照最大值从小到大排列。这样，\([4,1,6,2,5,3]\)
的标准循环表示法就是
\((4 2 1)(5)(6 3)\)。

定义好的排列：原排列和标准循环表示一致

寻找第k个字段序的好的排列

此题手玩n=4的样例可以发现：
“好的排列”只能由1..n的顺序排列通过以下操作得来：

在原排列上，选择若干个不相交的，长度为2的区间，然后翻转每个区间。
这个性质瞪眼法有点难瞪
长度为 n 的序列最多有几个好的排列？
n只能与n-1翻转，于是，对于一个排列，n要么和n-1翻转，要么不翻转
n和n-1翻转的话，即 \(f(n)+=f(n-2)\)
n不翻转的话，即 \(f(n)+=f(n-1)\)

这就是一个斐波那契的式子！
\(f(n) = f(n-1)+f(n-2)\)

然后我们递归的填数字就好了，递归写起来很简单，只是有点难想

#include<iostream>
#include<vector>
using namespace std;
#define ffp(x,y,z) for(ll (x)=(y);(x)<=(z);(x++))
#define ll long long int
#define q_ read()
inline ll read()
{ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();return x * f;
}void solve()
{ll n = q_;ll k = q_;vector<ll>fb(n + 2, 0);vector<int>num(n + 2, 0);fb[2] = fb[1] = 1;ffp(i, 3, n)fb[i] = fb[i - 1] + fb[i - 2];auto bud = [&](auto&& bud, int l,int r, ll nk)->void{if (l > r) { return; }if (l == r){num[l] = l;return;}int len = r - l + 1;//需要构造一个长度为len的，值为nk的数列if (nk <= fb[len])//可以放进len里面{num[l] = l;bud(bud, l + 1, r, nk);//把下面的全部翻转，然后翻转当前这个}else//太大了，需要翻转{num[l] = l+1;num[l + 1] = l;bud(bud, l + 2, r, nk - fb[len]);}};bud(bud, 1, n, k);ffp(i, 1, n)cout << num[i] << " \n"[i == n];
}int main()
{int t = 1;while (t--){solve();}return 0;
}