Description

【题意】
给定一个 1~n 的排列 p1,p2,…,pn，可进行若干次操作，每次选择两个整数 x,y，交换 px,py。
设把 p1,p2,…,pn 变成单调递增的排列 1,2,…,n 至少需要 m 次交换。
求有多少种操作方法可以只用 m 次交换达到上述目标。
因为结果可能很大，你只需要输出结果对 10^9+9 取模之后的值。
例如排列 2,3,1 至少需要2次交换才能变为 1,2,3。操作方法共有3种，分别是：
方法一：先交换数字2,3，变成 3,2,1，再交换数字3,1，变成 1,2,3。
方法二：先交换数字2,1，变成 1,3,2，再交换数字3,2，变成 1,2,3。
方法三：先交换数字3,1，变成 2,1,3，再交换数字2,1，变成 1,2,3。

【输入格式】
第一行包含整数T，表示一共有T组测试用例。
每个测试用例前都会有一个空行。
每个测试用例包含两行，第一行包含整数n。
第二行包含n个整数，表示序列p1,p2,…,pn。

【输出格式】
每个测试用例输出一个结果，每个结果占一行。

【数据范围】
1≤n≤10^5

【输入样例】
3

3
2 3 1

4
2 1 4 3

2
1 2

【输出样例】
3
2
1

思路：

对于一个排列p1,p2,p3……pn。如果从每个pi向i连一条边，那么可以得到一个n个点n条边的图，并且这个图由若干个环构成。

如下图，（2，4，1）构成一个环，（5，3）构成一个环，（6）独自构成一个环

不难发现我们的目的就是要让整张图变成n个自环。

引理：将一个长度为n的环变成n个自环，最少需要n-1次交换操作。

证明：每一次操作最多只能将一个环变成两个环，所以要将一个环变成n个环最少需要n-1次操作

设Fn为将一个长度为n的环变成n个自环，如果最初的排列是p1,p2,p3,……pn，由长度为l1,l2,l3……lk的k个环组成，其中l1+l2+l3……lk=n，那么最终的答案就是：

解释一下这个公式就是：

长度为l1,l2,l3……lk的k个环，分别最少可以通过li-1次操作变成li个自环，让题目给出的环变成自环，就是让k个环分别变成自环。由于各个环之间的操作互不相关，所以我们将各个环之间的操作方法混合到一起，得到出组合数就是答案。

因为每个环有li-1个操作，所以总共就有（l1-1)+(l2-1)+(l3-1)+……+(lk-1)=n-k 次操作，所以排列方式就有（n-k）！个。但是同一个环内的操作是不讲究排序的，因为它们都是一样的，所以就要挨个除去每个环内的排列方式，(l1-1)!、(l2-1)!、(l3-1)!……(lk-1)!，最后得到整道题的组合方式。

另外：这里直接给出Fn的通项公式：Fn=（其实我也不会证，但是这可以直接背下来了）

所以整道题就清晰明朗了，用快速幂来处理Fi，然后根据费马小定理，配合快速幂求出分母的乘法逆元，以方便求模。阶乘那些什么东西可以预处理一下。至于求环，可以直接用for来遍历，bk来标记，保证不重不漏。有一些特殊的东西也需要特判一下，要注意。

特别注意要分清楚概念：

• 变成自环的方案数是Fi
• 变成自环的步数是i-1

本题的收获就是：

• 将排列 p1,p2,…,pn变成递增序列的最小交换次数——先将其转化为环图，如果是长度为n的一环图，那么最少需要n-1次。
• 将排列 p1,p2,…,pn变成递增序列，保证最小交换次数下的方案数——先将自身转化为环图，如果是长度为n的一环图，那么就可套公式Fn=。如果不是，将自身拆分为若干个一环子图，每个子图的方案数相乘，并乘上每步操作的组合就是答案。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=1e9+9;
inline ll multi(ll a,ll b)
{ll ans=0;a%=mod;while(b){if(b&1)ans=(ans+a)%mod;a=(a+a)%mod;b>>=1;}return ans;
}
inline ll power(ll a,ll b)
{ll ans=1;a%=mod;while(b){if(b&1)ans=multi(ans,a);a=multi(a,a);b>>=1;}return ans;
}
int T,n,a[210000],k;
bool bk[210000];
ll ans,l[210000],fac[210000];
inline void sswap(int &x,int &y){int t=x;x=y;y=t;}
inline void pre()
{fac[0]=1;fac[1]=1;for(int i=2;i<=1e5;i++)fac[i]=multi(fac[i-1],i);
}
int main()
{scanf("%d",&T);pre();while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);memset(bk,false,sizeof(bk));memset(l,0,sizeof(l));ans=1;k=0;for(int i=1;i<=n;i++){if(bk[i]==true)continue;k++;for(int j=i;!bk[j];j=a[j])bk[j]=true,l[k]++;if(l[k]!=0 && l[k]!=1)ans=multi(ans,power(l[k],l[k]-2));ans=multi(ans,power(fac[l[k]-1],mod-2));}ans=multi(ans,fac[n-k]);printf("%lld\n",ans);}return 0;
}