题意
定义操作如下 : 用 \(0\cdots n-1\) 的一个排列 \({q_n}\) 交换排列 \({s_n}\) :
对 \(s_i\) 中的元素进行 \(n-1\) 次两两交换 , 第 \(i\) 次交换 \(s_{q_i}\) 和 \(s_{q_{i+1}}\) .
当 \(s_i=i\) 时 , 求排列 \(q_n\) 的个数 , 使得用 \(q_n\) 交换 \(s_n\) 得到给定的排列 \(p_i\) .
答案对 \(10^9+7\) 取模 .
数据范围 \(n\le 50\) , 来自一本通原题 .
数据范围 \(n\le 10^3\) , \(1s,256MB\) .
题解
显然得到每次交换操作相当于从交换位置断开了整个序列 , 此后无论如何操作 , 左右两边的元素不可能走到另一边 // 这种能够把问题分解的观察常常十分有用
这样 , 如果想要得到目标序列 , 单独看每一个数字的移动过程 , 都要求路径上前一个交换早于后面所有交换进行 , 当且仅当满足这一点能得出目标序列 . 这启发我们类似 CSP-2019 树上的数 一样的拓扑序视角看问题 . 因为每一个数字的移动过程产生的限制都可以用一个链描述 , 即前一个交换早于后一个 , 因此可以在 \(O(n^2)\) 的时间中得出 \(n-1\) 个相邻项交换之间的偏序关系 .
如何考虑计数 , 要求构造的是一个排列 , 而且后面的转移只和当前的最后一个交换的操作时间有关 , 经典地维护排列前 \(i\) 位的相对位置 .
简单描述一下这个 trick
就是说我们要构造一个排列的方案数 , 因为简单地研究每一个元素的排名的状态很大 , 所以转而对前 \(i\) 个元素描述一个 \(1 \cdots i\) 的排列表示这些元素之间的相对位置 , 每次加入新元素就枚举插入每个位置 , 并把后面的元素排名加一 .
这样做的好处是不用再考虑每一个排名是不是已经被前面的元素占据 , 从而可以只记录和转移有关的元素的相对排名 , 从而减少状态 .
对于这道题, 维护 \(f_{i,j}\) 表示前 \(i\) 个元素 , 其中第 \(i\) 个元素的排名是 \(j\) 的状态数 .
每次更新 \(i+1\) , 如果 \(i\) 早于 \(i+1\) :
\[f_{i+1,j}=\sum_{k=1}^{j-1} f_{i,j} \]如果 \(i\) 晚于 \(i+1\) :
\[f_{i+1,j} = \sum_{k=j}^{i} f_{i,j} \]如果没有限制关系直接全加一起 :
\[f_{i+1,j} = \sum_{k=1}^{i} f_{i,j} \]前缀和优化即可 \(O(n^2)\) 完成.
代码
#include<bits/stdc++.h>
#define file(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define int long long
#define INF 0x3f3f3f3f
#define INF64 1e18
using namespace std;
constexpr int N=5e3+5;
constexpr int p=1e9+7;
int a[N],n;
int f[N][N],b[N],s[N][N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) {int x;cin>>x;x++;a[x]=i;}
int ok=1;
for(int i=1;i<=n;i++){
if(a[i]>i){
for(int j=i;j<a[i]-1;j++){
if(b[j]==0) b[j]=1;
if(b[j]==2) ok=0;
}
}
else if(a[i]==i) ok=0;
else {
for(int j=a[i];j<i-1;j++){
if(b[j]==0) b[j]=2;
if(b[j]==1) ok=0;
}
}
}
if(!ok) {cout<<0;return 0;}
f[1][1]=1;
s[1][1]=1;
for(int i=2;i<n;i++){
for(int j=1;j<=i;j++){
if(b[i-1]==0){
f[i][j]=s[i-1][i-1];
}
if(b[i-1]==1){
f[i][j]=s[i-1][j-1];
}
if(b[i-1]==2){
f[i][j]=(p+s[i-1][i-1]-s[i-1][j-1])%p;
}
}
for(int j=1;j<=i;j++) s[i][j]=(s[i][j-1]+f[i][j])%p;
}
cout<<s[n-1][n-1];
}