C++全排列函数next_permutatio、perv_permutation()的使用

next_permutation

next_permutation函数STL里的函数，可以将一个数组按照从字典序小到大的顺序，生成全排列。返回的类型是bool类型，当没有下一个全排列时返回false；(必要时应该对数据进行排序，初始为字典序最小的那个排列，时间复杂度O(n))
prev_permutation()函数功能是输出所有比当前排列小的排列，顺序是从大到小

群友在排列数字

题意：

生成0~n-1的全排列，问组成的数有多少个可以整除k；

全排列函数代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[10];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        a[i]=i;
    }
    ll num,ans=0;
    do{
        num=0;
        for(int i=0;i<n;i++){
            num=num*10+a[i];
        }
        if(num%k==0) ans++;
    }while(next_permutation(a, a+n));
    if(!ans) cout<<"-1"<<endl;
    else cout<<ans<<endl;
    return 0;
}

当然也可以使用递归DFS求全排列来写，代码：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 7;
const int mod = 1e9+7;
int state[12];
ll cnt = 0, n, temp = 0, k;
void dfs(int deepth) {
    if(deepth == n) {
        if(temp != 0 && temp % k  == 0) ++cnt;
    }
    else {
        for(int i = 0; i < n; ++i) {
            if(!state[i]) {
                state[i] = 1;
                temp = temp * 10 + i;
                dfs(deepth+1);
                temp -= i;
                temp /= 10;
                state[i] = 0;
            }
        }
    }
}
int main(){
    cin >> n >> k;
    dfs(0);
    if(cnt != 0) cout << cnt << endl;
    else cout << -1 << endl;
    return 0;
}