Counting swaps acwing 212 (多重集的排列数)

题目地址

由题目，我们可以连接出 k 个环。单调递增排序只需拆分每个环，让每一个元素都变成自环。引理：把一个长度为n的环变成n个长度为1自环，最少需要操作n-1次。设$F_n$ 表示长度为n的自环变成n个长度为1的自环 的操作数有通项公式$F_n$ = $n^{n-2}$ 可以查阅资料，化简我不会，找出前几项，贴OEIS可以得到。那么整个序列的操作数为${\prod }_{l=1}^k{F}_l$ 再乘 $\frac{(n-k)!}{{\prod }_{l=1}^k(l-1)!}$ 前面表示整个所有环长的操作数之积 ， 后面表示所有步数的排序（多重集的排列数），对于同一个环里面的操作是不用考虑顺序的

即把操作顺序排好序后，再乘上每一个环可以操作的方法数。

代码：

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #include<bits/stdc++.h> #define int long long using namespace std; typedef pair<int,int> pii; typedef long long ll; const int INF = 0x3f3f3f3f; const double eps = 1e-4; const int mod = 1e9+9; const int N = 100010; int a[N],fact[N],infact[N]; bool vis[N]; int qmi(int a,int b){ int res = 1; while(b){ if(b&1) res = res*a%mod; a = a*a%mod; b >>= 1; } return res; } int dfs(int u){ if(vis[u]) return 0; vis[u] = true; return dfs(a[u])+1; } void init(){ fact[0] = infact[0] = 1; for(int i=1;i<=1e5;i++){ fact[i] = fact[i-1]*i%mod; infact[i] = infact[i-1]*qmi(i,mod-2)%mod; } } signed main(){ IOS; #ifdef ddgo freopen("C:/Users/asus/Desktop/ddgoin.txt","r",stdin); #endif init(); int tt; cin>>tt; while(tt --){ vector<int> ve; memset(vis,false,sizeof(vis)); int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) if(!vis[i]) ve.push_back(dfs(i));//存下环长 int sum = 1; for(int i=0;i<(int)ve.size();i++)//大于1的才操作 if(ve[i] != 1) sum = sum*qmi(ve[i],ve[i]-2)%mod*infact[ve[i]-1]%mod; sum = sum*fact[n-(int)ve.size()]%mod; cout<<sum<<endl; } return 0; }