题目描述

blablabla

样例

blablabla

算法1

(计数类DP——需要打表找规律) $O(nlogn)$

blablabla

时间复杂度分析：blablabla

C++ 代码

#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define int long long
typedef long long ll;

const int mod=1e9+9,N=1e5+10;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int f[N],jc[N],p[N];
bool vis[N];

template<typename T> inline void read(T &x){
    x=0;char f=1,c=getchar();
    while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
    x*=f;
}

int qpow(int x,int p){
    int ans=1;
    for(;p;p>>=1){
        if(p&1) ans=ans*x%mod;
        x=x*x%mod;
    }
    return ans;
}

signed main(){
    //freopen("input.txt","r",stdin);
    f[1]=f[2]=1;
    go(i,3,1e5) f[i]=qpow(i,i-2);
    jc[1]=jc[0]=1;
    go(i,2,1e5) jc[i]=jc[i-1]*i%mod;
    int T;read(T);
    while(T--){
        memset(vis,0,sizeof(vis));
        int n;read(n);
        int cnt=0,ans=1;
        go(i,1,n) read(p[i]);
        go(i,1,n){
            if(vis[i]) continue;
            int len=1;
            cnt++;
            for(int j=p[i];j!=i;j=p[j]) vis[j]=1,len++;
            ans=ans*f[len]%mod*qpow(jc[len-1],mod-2)%mod;
        }
        ans=ans*jc[n-cnt]%mod;
        cout<<ans<<endl;
    }   
    return 0;
}