【题解】间隔排列-C++

题目
Description
小Q是班长。在校运动会上，小Q班要进行队列表演。小Q要选出2*N名同学编队，每人都被编上一个号，每一个从1到N的自然数都被某2名同学佩戴，现在要求将他们排成一列，使两个编号为1的同学中间恰好夹1名同学，两个编号为2的同学中间恰好夹2名同学，……，两个编号为N的同学中间恰好夹N名同学，小Q希望知道这样的排法能否实现。
Input
输入文件仅包括一行，即要处理的N。N<=13
Output
输出有多少种排列顺序.
Sample Input
3
Sample Output
2

思路
这道题依然是DFS，每次搜索第dep个人放的位置，列举的范围从1到2n-dep-1，因为如果到2n-dep-1之后的位置，带有dep数字的两个人中间是无法隔dep个人的（前面都放了），所以就这样搜索下去。
当程序写完试运行时，我们发现N mod 4=1或2时，发现运行的时间较长，而其它情况下程序很快就找到可行解，我们就应该警觉到N mod4=1或2时，不存在可行解,下面我们证明N mod 4=1或2时，问题无解。
设问题的一个可行解为a1,a2,……,an,其中ai为标号为i的数字的位置，
这些数字它们对应数字的位置应该为a1+1+1,a2+2+1,……,an+n+1.这2N个整数a1,a2,……,an, a1+1+1,a2+2+1,……,an+n+1正是整数1,2,3，……,2N，因而
a1+a2+…+an+(a1+1+1)+(a2+2+1)+…+(an+n+1)
=

2(a1+a2+an)+n(n+1)/2+n=2n(2n+1)/2
2(a1+a2+…+an)=(3n2-n)/2
4(a1+a2+…+an)=n(3n-1)
可见n(3n-1)应该为4的倍数(上一排的等式推出)，当n mod 4=0,1,2,3时，n(3n-1) mod 4分别为0,2,2,0，故n mod 4=1或2时，不满足设的“有解”的前提，问题无解

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,cnt;
bool flag[66];
void ord(int per,int pla)
{
    flag[pla]=!flag[pla];
    flag[pla+1+per]=!flag[pla+1+per];
    return;
}
void dfs(int dep)
{
    if(dep>n)
    {
        cnt++;
        return;
    }
    for(int i=1;i<=2*n-dep-1;i++)
    {
        if(!flag[i]&&!flag[i+dep+1])
        {
            ord(dep,i);
            dfs(dep+1);
            ord(dep,i);
        }
    }
}
int main()
{
    cin>>n;
    if(n%4==1||n%4==2)
    {
        cout<<0<<endl;
        return 0;
    }
    dfs(1);
    cout<<cnt<<endl;
    return 0;
 }