【洛谷P3672】小清新签到题 | Mrsrz's blog

DP

题目大意：

给定 $n,k,x$，求长度为 $n$ 的排列中，逆序对个数恰好为 $x$ 对的排列中，第 $k$ 小的排列。

题解：

考虑求出 $f[i][j]$ 表示长度为 $i$ 的排列，逆序对个数为 $j$ 的方案数。

转移时，考虑把大小为 $i+1$ 的数插入到排列中，根据不同位置能产生 $0\sim i$ 的贡献。

于是 $f[i][k]=\sum_{j=i-k+1}^k f[i-1][k]$。

这个的时间复杂度为 $O(n^4)$，容易用前缀和优化到 $O(n^3)$。

然后，我们要做的就是贪心地按位确定排列的每个位置。

考虑一个位置，如果其填上某个数后，剩下的数仍然能和之前的产生 $x$ 个逆序对，且方案数大于等于 $k$，则这个位置就填上这个数，否则跳过。

这里的贪心的复杂度是 $O(n^2)$ 的，所以总复杂度 $O(n^3)$。

注意一些细节：

1. 由于 $k$ 最大 $10^{13}$，因此在 DP 的时候，如果出现大于 $k$ 的可以改成 $k+1$ 防止爆long long。前缀和数组不能这么做。
2. 前缀和数组需要滚动数组，否则空间开不下。

Code：

#include<iostream>
using namespace std;
typedef long long LL;
const LL inf=1e14;
int n,x;
LL k,f[305][305*305/2],g[2][305*305/2];
inline void upd(LL&a,LL b){a=(a+b>inf)?inf:a+b;}
int ans[305];
bool vis[305];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k>>x;
    f[0][0]=1;
    for(int i=0;i<=x;++i)g[0][i]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=x;++j)
            upd(f[i][j],g[i&1^1][j]-(j>=i?g[i&1^1][j-i]:0)),g[i&1][j]=(j?g[i&1][j-1]:0)+f[i][j];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            if(f[n-i][x-(j-1)]>=k){
                ans[i]=j;
                x-=j-1;
                break;
            }else k-=f[n-i][x-(j-1)];
    }
    for(int i=1;i<=n;++i){
        int k=ans[i];
        for(int j=1;j<=n;++j)
            if(!vis[j])
                if(!--k){
                    vis[j]=1;
                    cout<<j<<' ';
                    break;
                }
    }
    return 0;
}