The 3rd Ucup Stage 2: M. Balance of Permutation

题目链接：https://contest.ucup.ac/contest/1699/problem/8529

题目大意：求长度为 $n$ 字典序排名为 $k$ 的满足 $\sum _{|p_i-i|}=b$ 的排列。

做法

一开始看到数据范围这么小，下意识觉得可能是某种非常 interesting 的 meet in middle ，然后再优化了大半天状态以后发现好像可以直接多项式 $dp$ ，真是闹麻了。

注意到一个事情，如果观察 $\ge k$ 的数字和位置，可以发现有两种状态：空着和已经填上了，而且数字和位置同一状态的数量是一样的。

可以注意到，空着的数字或者位置总是要填的，而由于我们是按顺序枚举的，所以其的贡献已经可以算了，他们在绝对值中一定是大减小中的大者，按照这个思路直接 $dp$ 就行了。

单次枚举的时间复杂度是 ：$O(n^4)$ ，然后填数是 $O(n^2)$ 的，不过填数是从左到右的，方便起见，枚举也可以从小到大枚举。

这样就是 $O(n^6)$ 的。

代码也不难写。

但是呢，队长说题解的复杂度好像是 $O(n^5)$ 的，于是我接着想。（虽然后面看了题解发现是 $O(n^6)$ 的）

注意到一个事情，什么 $n$ 是可以被优化掉的，就是枚举这个位置放什么，我们可以锁住这个位置，不让这个位置放东西，然后前缀 $dp$ 一遍，后缀 $dp$ 一遍，当我要放 $val$ 的时候，就把 $val-1$ 的前缀和 $val+1$ 的后缀拿出来求出这个的贡献，就能优化掉一个 $n$ 。

原理类似于本来 $dp$ 合并是一个卷积，但是如果只用求特定项的系数，就可以线性求出。

最终时间复杂度：$O(n^5)$ 。

然后我就喜提 5.4k 。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef __int128 IT;
const int N = 35;
// >=  and  <
template<class T>
void getz(T &x){
    x = 0;
    char c = getchar();
    while(c > '9' || c < '0') c = getchar();
    while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c - '0'), c = getchar();
}
IT fl[N * 2][N][N * N * 2], fr[N * 2][N][N * N * 2], fc[N];
int v0[N], v1[N];
int vsl0[N][N], vsl1[N][N]; //<=
int vsr0[N][N], vsr1[N][N]; //>=
int n, S, a[N], Sb;
IT K;
void init(int ban){
    for(int l = 1; l <= n; l++){//limit
        for(int i = 1; i <= n; i++){
            vsl0[l][i] = vsl0[l][i - 1] + ((i == ban) || (v0[i] && v0[i] >= l));
            vsl1[l][i] = vsl1[l][i - 1] + (v1[i] && v1[i] >= l);
        }
        for(int i = n; i >= 1; i--){
            vsr0[l][i] = vsr0[l][i + 1] + ((i == ban) || (v0[i] && v0[i] <= l));
            vsr1[l][i] = vsr1[l][i + 1] + (v1[i] && v1[i] <= l);
        }
    }
}

void addposleft(int t, int id, int ban){//id - 1 -> id;
    for(int i = 0; i <= n / 2 + 1; i++){
        for(int s = 0; s <= Sb + Sb + Sb; s++){
            if(!fl[id - 1][i][s]) continue;
            if(t == ban || v0[t]){
                if(t == ban || v0[t] >= t) /*-*/ fl[id][i + 1][s - t] += fl[id - 1][i][s];
                else /*+*/ fl[id][i][s + t] += fl[id - 1][i][s];
                    
            }
            else{
                fl[id][i + 1][s - t] += fl[id - 1][i][s];//-
                if(i) fl[id][i][s + t] += fl[id - 1][i][s] * (i - vsl1[t][t - 1]);//+
            }
        }
    }
}
void addnumleft(int t, int id){
    for(int i = 0; i <= n / 2 + 1; i++){
        for(int s = 0; s <= Sb + Sb + Sb; s++){
            if(!fl[id - 1][i][s]) continue;
            if(v1[t]){
                if(v1[t] > t) /*-*/ fl[id][i][s - t] += fl[id - 1][i][s];
                else /*+*/ fl[id][i - 1][s + t] += fl[id - 1][i][s];
                    
            }
            else{
                fl[id][i][s - t] += fl[id - 1][i][s];//-
                if(i) fl[id][i - 1][s + t] += fl[id - 1][i][s] * (i - vsl0[t][t]);//+
            }
        }
    }
}
void addnumright(int t, int id){
    for(int i = 0; i <= n / 2 + 1; i++){
        for(int s = 0; s <= Sb + Sb + Sb; s++){
            if(!fr[id + 1][i][s]) continue;
            if(v1[t]){
                if(v1[t] <= t) /*+*/ fr[id][i + 1][s + t] += fr[id + 1][i][s];
                else /*-*/ fr[id][i][s - t] += fr[id + 1][i][s];
                    
            }
            else{
                fr[id][i + 1][s + t] += fr[id + 1][i][s]; //+
                if(i) fr[id][i][s - t] += fr[id + 1][i][s] * (i - vsr0[t][t + 1]); //-
            }
        }
    }
}
void addposright(int t, int id, int ban){//id + 1 -> id;
    for(int i = 0; i <= n / 2 + 1; i++){
        for(int s = 0; s <= Sb + Sb + Sb; s++){
            if(!fr[id + 1][i][s]) continue;
            if(t == ban || v0[t]){
                if(t == ban || v0[t] < t) /*+*/ fr[id][i][s + t] += fr[id + 1][i][s];
                else /*-*/ fr[id][i - 1][s - t] += fr[id + 1][i][s];
                    
            }
            else{
                fr[id][i][s + t] += fr[id + 1][i][s]; //+
                if(i) fr[id][i - 1][s - t] += fr[id + 1][i][s] * (i - vsr1[t][t]); //-
            }
        }
    }
}

int main(){
    cin.sync_with_stdio(false);
    cin.tie(0);
    getz(n); Sb = n * (n + 1) / 2;
    getz(S);
    getz(K);
    fc[0] = 1; for(int t = 1; t <= n; t++) fc[t] = fc[t - 1] * t;
    for(int t = 1; t <= n; t++){
        memset(fl, 0, sizeof(fl));
        memset(fr, 0, sizeof(fr));
        fl[0][0][Sb] = 1;
        fr[n + n + 1][0][Sb] = 1;

        v0[t] = -1;
        init(t);
        for(int i = 1; i <= n; i++){
            addposleft(i, i * 2 - 1, t);
            addnumleft(i, i * 2);
        }
        for(int i = n; i >= 1; i--){
            addnumright(i, i * 2);
            addposright(i, i * 2 - 1, t);
        }
        for(int i = 1; i <= n; i++){
            if(v1[i]) continue;
            int l = i * 2 - 1, r = i * 2 + 1;
            IT now = 0;
            for(int jl = 1; jl <= n / 2 + 1; jl++){
                IT k;
                int jr, c;
                if(i < t){
                    if(jl - vsl0[i][i] < 0 || jl - 1 - vsl1[i + 1][i - 1] < 0) continue;
                    jr = jl;
                    k = fc[jl - vsl0[i][i]] * fc[jl - 1 - vsl1[i + 1][i - 1]];
                    c = -i;
                }
                else{
                    if(jl - 1 - vsr0[i][i + 1] < 0 || jl - 1 - vsr1[i][i + 1] < 0) continue;
                    jr = jl - 1;
                    k = fc[jl - 1 - vsr0[i][i + 1]] * fc[jl - 1 - vsr1[i][i + 1]];
                    c = i;
                }
                for(int sl = 0; sl <= Sb + Sb + Sb; sl++){
                    int sr = Sb + Sb + S - (sl + c);
                    if(sr > Sb + Sb + Sb || sr < 0) continue;
                    if(fl[l][jl][sl] && fr[r][jr][sr]){
                        now += fl[l][jl][sl] * fr[r][jr][sr] * k;
                    }
                }
            }
            if(now < K) K -= now;
            else{
                v0[t] = i;
                v1[i] = t;
                break;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        cout << v0[i] << " ";
    }
    cout << "\n";
    return 0;
}

不过会长的最主要原因是有 $4$ 个长的几乎一样但是又不能合并的函数。

真是艹了。

官方题解和 $n^6$ 的做法基本一样，在此不再赘述。

但是有个问题，$n^6$ 我会写多长呢？

答案是 2.2k 。

#include<bits/stdc++.h>
using namespace std;
typedef __int128 IT;
const int N = 35;
IT dp[2][N][N * N * 2];
void sw(){
    swap(dp[0], dp[1]);
    memset(dp[0], 0, sizeof(dp[0]));
}
int base;
int n, B;
IT K;
void getz(auto &x){
    x = 0;
    char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c <= '9' && c >= '0') x = (x << 3) + (x << 1) + (c - '0'), c = getchar();
}
int m1[N], m2[N];// 1 : seat , 2 : number
int c1[N], c2[N];
IT solve(){
    for(int i = 1; i <= n; i++){
        c1[i] = 0;
        for(int j = 1; j <= i; j++) c1[i] += (m1[j] && m1[j] >= i);
    }
    for(int i = 1; i <= n; i++){
        c2[i] = 0;
        for(int j = 1; j < i; j++) c2[i] += (m2[j] && m2[j] >= i);
    }
    sw();
    dp[0][0][base] = 1ll;
    for(int i = 1; i <= n; i++){
        sw();
        for(int j = 0; j < i; j++){
            for(int k = 0; k <= base * 3; k++){
                if(!dp[1][j][k]) continue;
                if(!(m1[i] && m1[i] < i) && k >= i) dp[0][j + 1][k - i] += dp[1][j][k]; //-
                if(!(m1[i] && m1[i] >= i)){
                    if(m1[i]) dp[0][j][k + i] += dp[1][j][k];
                    else dp[0][j][k + i] += dp[1][j][k] * (j - c2[i]);
                }
            }
        }
        sw();
        for(int j = 0; j <= i; j++){
            for(int k = 0; k <= base * 3; k++){
                if(!dp[1][j][k]) continue;
                if(!(m2[i] && m2[i] <= i) && k >= i) dp[0][j][k - i] += dp[1][j][k];
                if(!(m2[i] && m2[i] > i)){
                    if(m2[i]) dp[0][j - 1][k + i] += dp[1][j][k];
                    else dp[0][j - 1][k + i] += dp[1][j][k] * (j - c1[i]);
                }
            }
        }
    }
    return dp[0][0][base + B];
}
int main(){
    getz(n); getz(B); getz(K);
    base = n * (n + 1) / 2;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(m2[j]) continue;
            m1[i] = j;
            m2[j] = i;
            IT rk = solve();
            if(rk < K) K -= rk;
            else break;
            m1[i] = 0;
            m2[j] = 0;
        }
    }
    for(int i = 1; i <= n; i++) cout << m1[i] << " ";
    cout << "\n";
    return 0;
}

短了一半，好写多了，真是艹了。

但是还是有点长，学习一下：

//https://contest.ucup.ac/submission/442419
#include <bits/stdc++.h>
using namespace std;
using i128=__int128;
const int N=31;
int n,b,g[N],p[N];
i128 f[N][N][N*N];
string K;
i128 val(){
	memset(f,0,sizeof f);
	int cnt=0,m=n;
	for(int i=1;i<=n;i++) if(p[i]) cnt+=abs(i-p[i]),m--;
	f[0][0][0]=1;
	for(int i=1;i<=n;i++){
		int c0=0,c1=0,t0=0,t1=0;
		for(int j=1;j<i;j++) c0+=!p[j],c1+=!g[j];
		t0+=c0+(!p[i]);t1+=c1+(!g[i]);
		for(int j=0;j<=min(t0,t1);j++) for(int t=t0+t1-j*2,k=t;k<=b-cnt;k++){
			f[i][j][k]=f[i-1][j][k-t];
			if(!g[i]&&j) f[i][j][k]+=(c0-j+1)*f[i-1][j-1][k-t];
			if(!p[i]&&j) f[i][j][k]+=(c1-j+1)*f[i-1][j-1][k-t];
			if(!g[i]&&!p[i]&&j) f[i][j][k]+=f[i-1][j-1][k-t];
			if(!g[i]&&!p[i]&&j>1) f[i][j][k]+=(c0-j+2)*(c1-j+2)*f[i-1][j-2][k-t];
		}
	}
	return f[n][m][b-cnt];
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>b>>K;
	i128 k=0;
	for(auto x:K) k=k*10+x-'0';
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(!g[j]){
		g[j]=i;p[i]=j;
		i128 cnt=val();
		if(cnt>=k){
			cout<<j<<" ";
			break;
		}
		k-=cnt;g[j]=0;
	}
	return 0;
}

$dp$ 外的部分没什么区别，但是 $dp$ 内的部分有很大区别，区别主要有 $3$ 个。

1. 我第二维记录的是还没成对的位置和数字，这有一个问题，虽然这两个数量确实相等，但是由于未成对里面可能有已经成对但是还没添加进来的数字或位置，这就导致在后面计算乘的系数的时候比较麻烦。

   而他记录的是已经成了多少对（忽略外面成对的数字），这样遇到已经在外面成对的数字或者位置可以直接跳过，甚至后面计算系数也好算。

2. 第三维，我记录的是每个数字的贡献，因此基础下标是 $\frac{n(n+1)}{2}$ ，但是他的贡献是实时算的，什么意思呢，就是如果我有 $k$ 个数字或位置在下面，每次往上移动一格，贡献为 $k$ ，而且忽略了外面成对数字的贡献，好处就是成对的数字或者位置可以直接跳过，而且 $dp$ 范围非常的自然。

3. 我添加数字或者位置写了两个循环，但是他是合并了，至于这个，我觉得没有优劣之分。

   主要是这两个添加时的判断都很少，所以合并起来也少。但是如果两个添加时有很多判断，合并起来实现复杂度是乘一起的。相比之下，虽然我的做法多了一层循环，但是条理更加清晰，犯错概率更低，所以我的代码之所以比他长，我觉得主要原因是前两条，而不是这一条，我觉得这一条各有优劣，没有对错之分。

还是实现麻烦了，还得学，还得多练。