组合数进阶-Counting Swaps

对于一个排列p，交换多少次变成1，2，3单调递增的排列。

啥事排列，就是n个数，这n个数由1到n的自然数组成。

将 p[i] 与 i 连接可以形成若干个圈。

。

对于每个圈交换次数为圈长度n减一。（不会证）

后面的思路要用到证明，请参考进阶指南。

将一个圈中的任意两个点交换会形成两个圈，只把一个圈的n-1与其他圈相乘并不能直接得到答案。

因为每一次交换两个点的方式可以不同。

用 $T(x,y)T(x,y)$ 表示将一个长度为 $n=x+yn=x+y$ 的环交换任意两个点拆成两个环长度为 $(x,y)(x,y)$ 的方式。

这是被拆的x和y各自需要交换的次数为x-1,y-1。根据乱七八糟组合数原理可知n环的方案为 $F_n={\sum }_{x+y=n}T(x,y)F_x{F}_y\left(\genfrac{}{}{0px}{}{n-2}{x-1}\right)F\_n=\backslash sum\_\{x+y=n\}\; T(x,y)F\_xF\_y\backslash binom\{n-2\}\{x-1\}$

总的方案为各环相乘在排列 $F_{l1}\cdot F_{l2}\cdot \mathrm{.}\mathrm{.}\mathrm{.}\cdot F_{lk}\cdot \frac{(n-2)!}{(l1-1)!(l2-1)!\mathrm{.}\mathrm{.}\mathrm{.}(lk-1)!}F\_\{l1\}\backslash cdot\; F\_\{l2\}\backslash cdot\; ...\backslash cdot\; F\_\{lk\}\backslash cdot\; \backslash frac\{(n-2)!\}\{(l1-1)!(l2-1)!...(lk-1)!\}$

如果你是神仙可以发现 $F(n)F(n)$ 可以变成一个公式 $F(n)=n^{n-2}F(n)=n^\{n-2\}$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100005,mod=1000000009;
ll fac[maxn],ni[maxn],f[maxn];
int n;
int a[maxn];
bool flag[maxn];
ll ksm(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
void init()
{
    int x=100000;
    fac[0]=1;
    for(int i=1;i<=x;i++)
        fac[i]=fac[i-1]*i%mod;
    ni[x]=ksm(fac[x],mod-2);//阶乘的倒数，也可以称为阶乘的逆元
    for(int i=x-1;i>=0;i--)
        ni[i]=ni[i+1]*(i+1)%mod;
    f[1]=f[2]=1;
    for(int i=3;i<=x;i++)
        f[i]=ksm(i,i-2);//由公式推出的f
}
int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        cin>>n;
        memset(flag,0,sizeof flag);
        for(int i=1;i<=n;i++)
            cin>>a[i];
        ll ans=1;
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(flag[i])
                continue;
            int s=1;
            for(int j=a[i]; j!=i; j=a[j])//dfs环
            {
                flag[j]=true;
                s++;
            }
            cnt++;
            ans=ans*f[s]%mod*ni[s-1]%mod;//圈长为s，可以先乘一个F然后除上s-1的阶乘
        }
        ans=ans*fac[n-cnt]%mod;//有cnt个长度大于1的圈，总共需要交换n-cnt次
        cout<<ans<<endl;
    }
    return 0;
}