问题描述

　　Piegirl终于发现了红色按钮，你现在还剩最后一个机会去改变这个结局。这个按钮下面的电路由n个从0到n-1编号节点组成。为了关闭这个按钮，这n个节点必须以特定的序列拆解。节点0必须首先拆解，在拆解了节点i后，下一个被拆解的节点必须是(2·i) mod n或(2·i)+1 mod n。最后一个被拆解的节点必须是节点0。节点0必须被拆解两次，其他节点必须刚好被拆解一次。你的任务是找到一个符合要求的顺序并输出它。如果没有任何一个顺序满足条件，输出-1。

 

输入格式

　　包含一个整数n(2<=n<=105)

 

输出格式

　　输出一个可以拆解所有节点的顺序。如果不可能输出-1。如果有多个可能的顺序，输出任意一个。

 

样例输入

数据1
2
数据2
3
数据3
4
数据4
16

样例输出

数据1
0 1 0
数据2
-1
数据3
0 1 3 2 0
数据4
0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 0

数据规模和约定

　　对于15%的数据2<=n<=10
　　对于30%的数据2<=n<=20
　　对于100%的数据2<=n<=10⁵

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+10;

int n;

int len;

int dist[maxn];

bool vis[maxn];

bool dfs(int k,int d)

{

    if(d==n-1&&(k*2==n||k*2+1==n))

    {

        dist[d]=k;

        dist[n]=0;

        return true;

    }

    dist[d]=k;

//    cout<<d<<" :"<<k<<endl;

    int ne=(k*2)%n;

    if(vis[ne]==false)

    {

        vis[ne]=true;

        if(dfs(ne,d+1))

            return true;

        vis[ne]=false;

    } 

    int nex=(k*2+1)%n;

    if(vis[nex]==false)

    {

        vis[nex]=true;

        if(dfs(nex,d+1))

            return true;

        vis[nex]=false;

    } 

    return false;

}

int main()

{

    int i,j;

    cin>>n;

    vis[0]=true;

    if(n&1)

        cout<<"-1"<<endl;

    else

    {

        if(dfs(0,0))

        {

            for(i=0;i<=n;i++)

            {

                if(i!=0)

                    cout<<" ";

                cout<<dist[i];

            }

        }

    }

    return 0;

}

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+10;

int n;

vector<int> dist;

bool vis[maxn];

void dfs(int k)

{

    vis[k]=true;

    if(!vis[(k*2)%n])

        dfs((k*2)%n);

    if(!vis[(k*2+1)%n])

        dfs((k*2+1)%n);

    dist.push_back(k);

}

int main()

{

    int i,j;

    cin>>n;

    vis[0]=true;

    if(n&1)

        cout<<"-1"<<endl;

    else

    {

        dfs(0);

        reverse(dist.begin(),dist.end());

        dist.push_back(0);

        for(i=0;i<dist.size();i++)

            cout<<dist[i]<<" ";

        cout<<endl;

    }

    return 0;

}