计数交换

这道题怎么可能简单--acwing评分乱搞啊...
首先得知道,把一个环拆成n个自环需要n-1步.然后把一个奇数环拆成两种不同的环x,y的方案数为n,把一个偶数环拆成x==y方案数为n/2,其他都是n.进一步打表可知结论,把一个大小为n的环拆成n个大小为1的自环可行种数为f[n]=n^(n-2).
然后xjb可以乱搞了--好难啊..

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int mod=1e9+9;
int a[N];
int vis[N];
int cnt[N];
int f[N];
int sum[N];//打表阶层
vector<int>v[N];

int qp(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void dfs(int pos,int fa,int color)
{
    if(vis[pos]) return;
    vis[pos]=color;
    for(int i=0;i<v[pos].size();i++)
    {
        if(v[pos][i]==fa) continue;
        if(!vis[v[pos][i]])dfs(v[pos][i],pos,color);
    }
}

signed main()
{
    sum[0]=1;
    for(int i=1;i<=N;i++)
    {
        sum[i]=sum[i-1]*i%mod;
    }
    int T;
    cin>>T;
    while(T--)
    {
        //输入
        int n;
        memset(cnt,0,sizeof cnt);
        memset(vis,0,sizeof vis);
        cin>>n;
        for(int i=1;i<=n;i++) v[i].clear();
        for(int i=1;i<=n;i++)   scanf("%lld",&a[i]);
        //建边
        for(int i=1;i<=n;i++)
        {
            v[i].push_back(a[i]);
            v[a[i]].push_back(i);
        }
        //进行染色
        int k=1;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                dfs(i,i,k);
                k++;
            }
        }
        k--;
        //统计染色状况
        for(int i=1;i<=n;i++)
        {
            cnt[vis[i]]++;
        }
        //处理f数组
        int vv=1;
        for(int i=1;i<=k;i++)//f[i]=cnt[i]^(cnt[i]-2).
        {
            if(cnt[i]<2) f[i]=1;
            else f[i]=qp(cnt[i],(cnt[i]-2));
            vv=vv*f[i]%mod;
        }
        //ans就是(n-k)!/((cnt[1]-1)!*(cnt[2]-1)!...(cnt[k]-1)!)*(f[1]*f[2]*...*f[k]).
        int ans,lv;
        int res=1;
        for(int i=1;i<=k;i++)
        {
            res=res*sum[cnt[i]-1]%mod;
        }
        lv=qp(res,mod-2);
        ans=sum[n-k]*vv%mod*lv%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

这个复杂度建议大家照着写,不然不小心就t了hhh

.