题解：P13795 [SWERC 2023] Flag performance
JZJR_A_0
·
·
题解
前置知识
题意
给你一个 N 的排列，问 K 次操作后让排列单调递增的本质不同方案数有多少，多测。
## Part1
思考一个问题，怎么求最小操作数。
这是一个经典结论，考虑 $i$ 向 $p_i$ 连边，那么最后的答案就是图中所有环大小 $-1$ 之和。
这是显然的，考虑原本的一次交换的 $x,y$ 在同一个环上，此时交换等价于断成两个不同的环，不难证明上述正确。
考虑推广一下，此时如果不在相同环上，是等价与连环的。
那么我们现在就有一个想法，从结束状态转移回给定状态来确定答案数。
## Part2
一个朴素的想法是记录当前操作数与不同大小环个数状态。
但是 $N\leq 30$，如果朴素的 DP 会是 $N^N$ 难以通过。
事实上，我们的状态数实则很小，打表发现实际状态数只有大概 $6000$ 种，下文钦定其为 $S$。
那么我们就可以用 `map<vector<int>,int>` 来优化状态。
不难发现可以预处理，每次再把重复部分除掉即可。‘
转移分四种，考虑合并不同大小，合并相同大小，拆分成不同大小，拆分成相同大小。
现在我们就有 $O(N^2\cdot K\cdot S\cdot \log{NS} +TN)$ 的复杂度，可以通过。
## Part3
如果只有如此其实也就是个蓝。
事实上，这道题的数据范围可以放到 $K\leq 1000$，考虑如下优化。
首先可以将 `map` 换成 `unordered_map`，这需要手写 Hash。
其次我们发现实现过程中转移再 Hash 出来这一步其实是没有必要的，考虑对其预处理，实现精细可以将复杂度降到 $O(N\cdot K\cdot S)$。
## code:
实现较为简单。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int base=719;
const int N=35,K=1e3+5,M=1e4+5;
int n,T,p[N];
struct Hash {
unsigned long long operator()(const vector<int>&v)const {
unsigned long long r=0;
for(int x:v) {
r=r*base+x;
}
return r;
}
};
unordered_map<vector<int>,int,Hash>id;
int tr[M][M];
vector<pair<int,int>>G[M];
int tot;
void dfs(const vector<int>&now) {
for(size_t i=0;i<now.size();i++) {
int x=now[i];
for(int j=1;j<x;j++) {
if(j>x-j)break;
vector<int>nxt=now;
nxt.erase(nxt.begin()+i);
nxt.push_back(j);
nxt.push_back(x-j);
sort(nxt.begin(),nxt.end());
if(!id.count(nxt)) {
id[nxt]=++tot;
dfs(nxt);
}
tr[id[now]][id[nxt]]+=(j*2==x)?(x/2):x;
}
}
for(size_t i=0;i<now.size();i++) {
for(size_t j=i+1;j<now.size();j++) {
vector<int>nxt=now;
nxt.erase(nxt.begin()+j);
nxt.erase(nxt.begin()+i);
nxt.push_back(now[i]+now[j]);
sort(nxt.begin(),nxt.end());
if(!id.count(nxt)) {
id[nxt]=++tot;
dfs(nxt);
}
tr[id[now]][id[nxt]]+=now[i]*now[j];
}
}
}
int f[M][K];
struct DSU {
int fa[N],sz[N];
void init() {
for(int i=1;i<=n;i++) {
fa[i]=i;
sz[i]=1;
}
}
int find(int x) {
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y) {
x=find(x);
y=find(y);
if(x==y)return;
fa[x]=y;
sz[y]+=sz[x];
}
}dsu;
void init() {
vector<int>S={n};
id[S]=++tot;
dfs(S);
for(int u=1;u<=tot;u++) {
for(int v=1;v<=tot;v++) {
if(tr[u][v]) {
G[u].push_back({v,tr[u][v]%mod});
}
}
}
vector<int>all1;
for(int i=0;i<n;i++) {
all1.push_back(1);
}
f[id[all1]][0]=1;
for(int d=1;d<=1000;d++) {
for(int u=1;u<=tot;u++) {
for(auto[v,w]:G[u]) {
f[u][d]=(f[u][d]+f[v][d-1]*w)%mod;
}
}
}
}
void solve() {
int k;
cin>>k;
for(int i=1;i<=n;i++) {
cin>>p[i];
}
dsu.init();
for(int i=1;i<=n;i++) {
dsu.merge(i,p[i]);
}
vector<int>cur;
for(int i=1;i<=n;i++) {
if(dsu.find(i)==i) {
cur.push_back(dsu.sz[i]);
}
}
sort(cur.begin(),cur.end());
cout<<f[id[cur]][k]<<"\n";
}
signed main() {
// system("fc ex_perm4.out perm.out");
// freopen("ex_perm4.in","r",stdin);
// freopen("perm.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>T;
init();
while(T--) solve();
return 0;
}
```