首页 文章 逆康托展开-模板

逆康托展开-模板

2023-03-03 19:53  浏览数:460  来源:Coat    

#define _CRT_SECURE_NO_WARNIGNS
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N = 10010, inf = 0x3f3f3f3f;
ll n, m, ans, sum, res, mx, mn;
ll h[N], s[N],dp[N][N],p[N][N],val_fac[N],step_1[N],val_pow[N];
void decontor(ll n, ll p)
{
vector<ll>mus, ans;
ll now = p - 1;
for (ll i = 1; i <= n; i++)
mus.push_back(i);
for (ll i = n; i >= 1; i--)
{
int l = now / val_fac[i - 1];
now = now % val_fac[i - 1];
ans.push_back(mus[l]);
mus.erase(mus.begin() + l);
}
for (ll i = 0; i < n; i++)
step_1[i + 1] = ans[i];
}
ll Digit(ll num)
{
ll sum = 0;
while (num)
{
num /= 10;
sum++;
}
return sum;
}
void solve()
{
ll pp;
cin >> n>>pp;
val_fac[0] = 1;
val_pow[0] = 1;
for (ll i = 1; i <= 15; i++)
val_fac[i] = val_fac[i - 1] * i;
ll dig = Digit(n);
for (ll i = 1; i <= dig; i++)
val_pow[i] = val_pow[i - 1] * 2;
if (pp > val_fac[min(n, (ll)13)])
{
cout << -1 << endl;
return;
}
decontor(min(n, (ll)13), pp);
for (int i = 0; i <= n; i++)
cout << step_1[i]<<' ';
cout << endl;
}
int main()
{
int T = 1;
cin >> T;
while (T--)
{
solve();
}
}



声明:以上文章均为用户自行添加,仅供打字交流使用,不代表本站观点,本站不承担任何法律责任,特此声明!如果有侵犯到您的权利,请及时联系我们删除。

字符:    改为:
去打字就可以设置个性皮肤啦!(O ^ ~ ^ O)