【NEUQ】 H Lethe的手环 【圆周排列生成】or【DFS 剪枝】

题目描述：
Lethe最近买了一个新的手环，想送给女友。但他觉得只送一个手环还不够诚意，于是他决定在手环上镶嵌一些钻石。已知这个手环有n个孔可以镶嵌，且这n个孔均匀分布在手环上。Lethe是一个有强迫症的人，于是他买了价值为1、2。。。n的钻石各一个。但是他了解到他的女友不喜欢7这个数字，所以他决定任意相邻的三个钻石价值之和不能为7的倍数。现在他不知道他有多少种顺序去镶嵌钻石，你能帮帮他吗？
输入：
多组输入 每行一个整数n（1<=n<=12），与描述相同
输出：
对于每组输入，输出方案数
1
2

1
1

分析 1： 根据圆周排列的规律，我们可以知道对于从n个不同物体中抽取n个进行圆周排序的不同的种类数为(n-1)! 。 所以对于这个题目，n最大12， 即11! ，所以我们可以进行暴力 ，很快出答案。
这里我们如何暴力呢？ 如果直接遍历n！的话，如何处理相同的情况？所以这里有个好办法，我们可以固定一个数字不动，将其余的数字进行全排列，这样就是不重复的遍历所有的情况，然后我们再处理如果任意三个数字是不是7的倍数情况就行了。
看代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int arr[15];
void solve(int n){
    for(int i=1;i<=n;i++)  arr[i]=i ;
    LL ans=0;
    do{
        //for(int i=1;i<=n;i++) printf("%d ",arr[i]); puts("");
        int flag=1;
        for(int i=1;i<=n-2;i++) {
            if( (arr[i]+arr[i+1]+arr[i+2] )%7==0) {
                flag=0; break;
            }
        }
        if((arr[n-1]+arr[n]+arr[1]) %7==0) flag=0;
        if((arr[n]+arr[1]+arr[2])%7==0) flag=0;

        if(flag) ans++;
    }while(next_permutation(arr+2,arr+1+n)) ;  // 固定1不动，全排列其余的。
    printf("%lld,",ans);  // 根据圆周排列 可知n个不同数字排圆排列，不重复的有 (n-1)! 种情况。
}
void init(){  //遍历代码
    int n=12;
    for(int i=1;i<=n;i++){
        solve(i);
    }
}
int ans[15]={0,1,1,2,0,12,84,192,1216,8608,66032,529376,5187584};
int main(){
    //init();
    int n;
    while(scanf("%d",&n)!=EOF) printf("%d\n",ans[n]);
return 0;
}

分析二 ： 还是要利用固定一个不动，然后全排列剩下的数字遍历所有的不同情况，不过这个遍历可以用dfs来实现，同时 为了减少时间，我们在生成全排列的过程中，将相邻的三个数字和是7的倍数的剪枝掉。
代码

#include<bits/stdc++.h>
using namespace std;

int a[20],b[20];
bool vis[20];
int n,ans;
void dfs(int now,int id){
    vis[now]=true; b[id]=now;
    if(id>=3) { //生成排列的途中进行 剪枝
        if((b[id-2]+b[id-1]+b[id] )%7==0) return ;
    }
    if(id==n) {  // 一个排列完成
        //for(int i=1;i<=n;i++) printf("%d ",b[i]);puts("");
        if(n>=3){
            if((b[n-1]+b[n]+b[1])%7==0) return ; // 环形的判定
            if((b[n]+b[1]+b[2])%7==0)   return ;
            ans++;
        }
        else ans++;
        return ;
    }

    for(int i=2;i<=n;i++){
        if(!vis[i]){
            dfs(i,id+1);
            vis[i]=false;
        }
    }
}
int main(){
    while(cin>>n){
        memset(vis,false,sizeof(vis));
        for(int i=1;i<=n;i++) a[i]=i;
        ans=0; dfs(1,1);
        printf("%d\n",ans);
    }
return 0;
}