https://www.luogu.org/problemnew/show/P1379
#include <bits/stdc++.h>
using namespace std;
#define ll long long static const int fac[] = {, , , , , , , , , ,}; // 阶乘 //康托展开
int cantor(int *a,int n)
{
int code=;
for(int i=;i<n;i++)
{
int x=;int c=,m=;//c记录后面的阶乘
for(int j=i+;j<n;j++)
{
if(a[j]<a[i])x++;
m*=c;c++;
}
code+=x*m;
}
//printf("cantor=%d\n",code);
return code;
} //逆康托展开
void decantor(int code,int *a,int n){
bool vis[]={};
for(int i=;i<n;i++){
int r = code / fac[n-i-];
code %= fac[n-i-];
int cnt = ;
int j;
for(j=;j<=n;j++){
if(vis[j]==){
cnt++;
if(cnt==r+){
a[i]=j;
vis[j]=;
break;
}
}
}
} /*printf("decantor=");
for(int i=0;i<n;i++){
printf(" %d",a[i]);
}
printf("\n");*/
} struct dat
{
int cur;
int pre;
} d,dt,data[]; queue<dat> q; void show(dat d)
{
//cout<<"s"<<endl;
stack<int> s;
s.push(d.cur);
while()
{
if(d.pre==-)
break;
s.push(d.pre);
d=data[d.pre];
} printf("%d\n",s.size()-);
} int s,t; inline bool found(int code)
{
return (code==t);
} int up(int code){
int a[];
decantor(code,a,);
for(int i=;i<;i++){
if(a[i]==){
if(i>=){
swap(a[i],a[i-]);
return cantor(a,);
}
}
}
return -;
} int down(int code){
int a[];
decantor(code,a,);
for(int i=;i<;i++){
if(a[i]==){
if(i<=){
swap(a[i],a[i+]);
return cantor(a,);
}
}
}
return -;
} int right(int code){
int a[];
decantor(code,a,);
for(int i=;i<;i++){
if(a[i]==){
if(i%!=){
swap(a[i],a[i+]);
return cantor(a,);
}
}
}
return -;
} int left(int code){
int a[];
decantor(code,a,);
for(int i=;i<;i++){
if(a[i]==){
if(i%){
swap(a[i],a[i-]);
return cantor(a,);
}
}
}
return -;
} void bfs()
{
memset(data,-,sizeof(data)); d.cur=s;
d.pre=-;
data[d.cur]=d; if(found(d.cur))
{
printf("0\n");
return;
}
q.push(d); while(!q.empty())
{
d=q.front();
q.pop(); dt.cur=up(d.cur);
if(dt.cur!=-&&data[dt.cur].cur==-){
dt.pre=d.cur;
data[dt.cur]=dt;
if(found(dt.cur)){
show(dt);
return;
}
q.push(dt);
} dt.cur=down(d.cur);
if(dt.cur!=-&&data[dt.cur].cur==-){
dt.pre=d.cur;
data[dt.cur]=dt;
if(found(dt.cur)){
show(dt);
return;
}
q.push(dt);
} dt.cur=left(d.cur);
if(dt.cur!=-&&data[dt.cur].cur==-){
dt.pre=d.cur;
data[dt.cur]=dt;
if(found(dt.cur)){
show(dt);
return;
}
q.push(dt);
} dt.cur=right(d.cur);
if(dt.cur!=-&&data[dt.cur].cur==-){
dt.pre=d.cur;
data[dt.cur]=dt;
if(found(dt.cur)){
show(dt);
return;
}
q.push(dt);
}
} cout<<"NOFOUND"<<endl;
} int main()
{
int a[]={,,,,,,,,};
for(int i=; i<; i++)
a[i]++;
t=cantor(a,); for(int i=; i<; i++)
scanf("%1d",&a[i]); s=cantor(a,);
//decantor(t,a,8); bfs();
}