H - Little T2 and Derangements Gym - 101864H（第k个错排排列，状压DP）

题意：
$i$不在第$i$个位置的排列称为错排排列，
求按字典序第$k$个错排排列。
$2\le n\le 100,k\le 1e15$。

思路；
对于这类第$k$个排列的问题，都可以想到，只需要很少的数，就可以构造出很多排列。尽管本题$n$范围达到100，但实际上最多考虑20个数字就够了。

我们先按照错排公式$num[i]=(n-1)\ast (num[i-1]+num[i-2])$，算出实际要考虑多少个数字。那么前面不需要考虑的数字，只需要邻项交换就好了。

定义$f[need][sta]$代表$need$个数字的排列，且前面一些数字已经放置在了最前面的方案数，$sta$状态代表放置了哪些数字在最前面。

那么问题就和普通的求第$k$个排列问题一样，我们从前往后每个位置枚举数。枚举当前位置放置$i$的方案数$now$，如果$now<k$，那么说明不能放$i$，就有$k-=now$。如果$now\ge k$，那么说明这个位置放$i$足够满足这么多方案数，所以这个位置就是$i$。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <map>
using namespace std;
const int maxn = 105;
typedef long long ll;

ll num[maxn];//错排总数
ll f[20][(1 << 20) + 7];
void init() {
    num[0] = 1;num[1] = 0;
    for(int i = 2;i <= 20;i++) {
        num[i] = (i - 1) * (num[i - 1] + num[i - 2]);
    }
}
int get(int sta) {
    int cnt = 0;
    while(sta) {
        sta &= (sta - 1);
        cnt++;
    }
    return cnt;
}
ll DP(int need,int sta) {
//    printf("%d %dn",need,sta);
    if(f[need][sta] != -1) return f[need][sta];
    int pos = get(sta);
    if(pos == need) return 1;
    ll &ans = f[need][sta];
    ans = 0;
    for(int i = 0;i < need;i++) {
        if(i == pos) continue;
        if(sta & (1 << i)) continue;
        ans += DP(need,sta ^ (1 << i));
    }
    return ans;
}
void cal(int n,ll all) {
    int need = 0;
    for(int i = 1;i <= 20;i++) {
        if(num[i] >= all) {
            need = i;break;
        }
    }
    if((n - need) & 1) need++;
    vector<int>vec;
    int sta = 0;
    for(int i = 0;i < need;i++) { //第i个位置
        for(int j = 0;j < need;j++) { //放置第j个数字
            if(sta & (1 << j)) continue;
            if(i == j) continue;
            ll now = DP(need,sta ^ (1 << j));
            if(now < all) {
                all -= now;
            } else {
                vec.push_back(j);
                sta ^= (1 << j);
                break;
            }
        }
    }
    for(int i = 1;i <= n - need;i += 2) {
        printf("%d %d ",i + 1,i);
    }
    for(int i = 0;i < vec.size();i++) {
        printf("%d ",vec[i] + n - need + 1);
    }
    printf("n");
}
int main() {
    init();
    memset(f,-1,sizeof(f));
    int T;scanf("%d",&T);
    while(T--) {
        ll n,k;scanf("%lld%lld",&n,&k);
        cal(n,k);
    }
    return 0;
}

最后

以上就是粗心西牛为你收集整理的H - Little T2 and Derangements Gym - 101864H（第k个错排排列，状压DP）的全部内容，希望文章能够帮你解决H - Little T2 and Derangements Gym - 101864H（第k个错排排列，状压DP）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。