LG4778 Counting swaps
给定你一个 \(1\sim n\) 的排列 \(p\)，可进行若干次操作，每次选择两个整数 \(x,y\)，交换 \(p_x,p_y\)。
用最少的操作次数将给定排列变成单调上升的序列 \(1,2,\dots,n\)，有多少种方式呢？请你输出方式数对 \(10^9+9\) 取模的结果。
对于一个排列 \(p\)，如果 \(i\) 向 \(p_i\) 连边形成一张有向图，显然会形成若干个简单环，目标状态即 \(n\) 个自环。
将一个大小为 \(k\) 的环变成 \(k\) 个自环，至少需要 \(k-1\) 次交换（每次交换至多增加一个环）。
定义 \(f(i)\) 为将一个大小为 \(i\) 的环，在保证交换次数最小的情况下，有多少种方式将其变成目标状态。
考虑每次将一个环分割成两个环，分割出来的两个环大小为 \(x,y\)，分割方案有多少种。
显然当 \(x=y\) 的时候，环上有 \(i/2\) 对点，所以方案数为 \(i/2\)。
当 \(x\neq y\) 时候，环上可以选取 \(i\) 个点，每个点与顺时针方向的第 \(x\) 个点向匹配，方案数为 \(i\) 种。
同时分割成两个环之后，两个环内的操作是不会互相影响的，所以相当于有两种操作，第一种操作 \(x\) 个，第二种操作 \(y-1\) 个，最后的操作序列有多少种。即 \(\frac{(x+y-2)!}{(x-1)!(y-1)!}\) 种。综上就是
\[f(x)=\sum_{i=1}^{\lfloor x/2\rfloor} f_i\times f_{x-i}\times \frac{(x-2)!}{(i-1)!(x-i-1)!} \times \begin{cases}x \quad 2\times i\neq n\\ i \quad 2\times i=n\end{cases} \]然后求出来之后会发现 \(f(x)=x^{x-2}\)。
将所有环的答案合并，由于每个环之间操作时不会互相影响的，所以方案数乘上可重集的排列数（和上方同理）。
\[ans=(\prod_{i=1}^{k}f(siz_i))\times \frac{(n-k)!}{\prod_{i=1}^{k}(siz_i-1)!} \]总时间复杂度 \(O(n\log n)\)，复杂度瓶颈在快速幂求 \(f(x)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
const ll MOD=1000000009;
inline ll fpr(ll b,ll t=MOD-2,ll x=1){
for(;t>0;t>>=1,b=b*b%MOD)
if(t&1)x=x*b%MOD;
return x;
}
namespace binom{
const int RRN=1000006;
ll fac[RRN],ifc[RRN];
inline void binom_init(int n){
fac[0]=ifc[0]=1ll;
for(ll i=1;i<=n;++i)fac[i]=fac[i-1]*i%MOD;
ifc[n]=fpr(fac[n]);
for(ll i=n-1;i>=1;--i)ifc[i]=ifc[i+1]*(i+1)%MOD;
}
inline ll C(ll n,ll r){
if(n<r)return puts("114514"),-1;
return fac[n]*ifc[r]%MOD*ifc[n-r]%MOD;
}
}
using namespace binom;
const int N=1000006;
int n,p[N],tot;
ll f[N],top;bool vis[N];
inline void dfs(int loc){
vis[loc]=1;++tot;
if(!vis[p[loc]])dfs(p[loc]);
}
int main(){
binom_init(1000000);
int T;scanf("%d",&T);
while(T--){
scanf("%d",&n);
tot=top=0;
for(int i=1;i<=n;++i)vis[i]=0;
for(int i=1;i<=n;++i)scanf("%d",&p[i]);
for(int i=1;i<=n;++i){
if(!vis[i]){
int las=tot;
dfs(i);
f[++top]=tot-las;
tot=las;
}
}
ll ans=fac[n-top];
for(int i=1;i<=top;++i)ans=ans*fpr(f[i],f[i]-2)%MOD;
for(int i=1;i<=top;++i)ans=ans*ifc[f[i]-1]%MOD;
printf("%lld\n",ans);
}
return 0;
}