Liveddd's Blog

愛にできることはまだあるかい

P8338 [AHOI2022] 排列

发表于 分类于
本文字数： 5.7k 阅读时长 ≈ 13 分钟

并没有用到什么高深的知识。

对于一个排列，我们从 $i$ 向 $p_i$ 连边，会得到若干个置换环。答案就是新的置换环的大小的 $\text{lcm}$。容易发现 $a_i^{(k)}=j$ 当且仅当 $i,j$ 属于同一个置换环。否则的话，交换 $i,j$，会将 $i,j$ 分属于的两个置换环合并为一个。

答案只与置换环的大小有关。并且大小不同的置换环最多有 $\mathcal O(\sqrt{n})$ 个。所以说可以直接暴力枚举两个置换环的大小。至于求 $\text{lcm}$，我们需要分解质因数来求，因为有值域的限制，利用筛法分解质因数容易做到单次 $\mathcal O(\log n)$。开一个桶来维护所有质因子的最大幂。枚举两个置换环时最多会影响两个值，所以桶中记录前三大的值即可。时间复杂度 $\mathcal O(n\log n)$。

随便写写就好。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5+10,P=5e4+10,mod=1e9+7;
template <class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}

int T,n,m;
int cnt,prime[P],g[N];
bool vis[N];
int a[N],b[N],c[N];
int p[P][3];
int ans,res;
inline int adj(int x){return x>=mod?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
inline void prework(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!g[i])prime[++cnt]=i,g[i]=cnt;
        for(int j=1;j<=cnt&&1ll*i*prime[j]<=n;j++)
        {
            g[i*prime[j]]=j;
            if(!(i%prime[j]))break;
        }
    }
}
inline void insert(int x)
{
    while(x>1)
    {
        int j=g[x],tot=0;
        while(!(x%prime[j]))x/=prime[j],tot++;
        if(tot>=p[j][0])
        {
            p[j][2]=p[j][1];
            p[j][1]=p[j][0];
            p[j][0]=tot;
        }
        else if(tot>=p[j][1])
        {
            p[j][2]=p[j][1];
            p[j][1]=tot;
        }
        else if(tot>=p[j][2])
            p[j][2]=tot;
    }
}
inline void del(int x)
{
    while(x>1)
    {
        int j=g[x],tot=0;
        while(!(x%prime[j]))x/=prime[j],tot++;
        if(tot==p[j][0])
        {
            res=1ll*res*qpow(qpow(prime[j],p[j][0]-p[j][1]))%mod;
            p[j][0]=p[j][1];
            p[j][1]=p[j][2];
            p[j][2]=0;
        }
        else if(tot==p[j][1])
        {
            p[j][1]=p[j][2];
            p[j][2]=0;
        }
        else if(tot==p[j][2])
            p[j][2]=0;
    }
}
inline void solve()
{
    // cout<<"T:"<<T<<"\n";
    memset(vis,0,sizeof(vis));
    memset(p,0,sizeof(p));
    memset(c,0,sizeof(c));
    m=0;
    read(n);
    for(int i=1;i<=n;i++)read(a[i]);
    for(int i=1;i<=n;i++)
    {
        if(vis[i])continue;
        int x=i,tot=0;
        do{vis[x]=1,x=a[x],tot++;}
        while(x!=i);
        b[++m]=tot;
        // cout<<tot<<" ";
    }
    for(int i=1;i<=m;i++)
    {
        int x=b[i];
        insert(x);
    }
    // cout<<"\n";
    // cout<<"m:"<<m<<"\n";
    sort(b+1,b+1+m);
    int pos=0;
    for(int i=1;i<=m;i++)
    {
        if(b[i]!=b[i-1])pos++;
        c[pos]++;
    }
    m=unique(b+1,b+1+m)-b-1;
    ans=0,res=1;
    for(int i=1;i<=cnt;i++)res=1ll*res*qpow(prime[i],p[i][0])%mod;
    int clone=res;
    // cout<<"res:"<<res<<"\n";
    // cout<<"m:"<<m<<"\n";
    for(int i=1;i<=m;i++)
    {
        if(c[i]==1)continue;
        int x=b[i]<<1;
        res=clone;
        del(b[i]),del(b[i]);
        while(x>1)
        {
            int j=g[x],tot=0;
            while(!(x%prime[j]))x/=prime[j],tot++;
            if(tot>p[j][0])res=1ll*res*qpow(prime[j],tot-p[j][0])%mod;
        }
        insert(b[i]),insert(b[i]);
        ans=adj(ans+1ll*c[i]*(c[i]-1)%mod*b[i]%mod*b[i]%mod*res%mod);
    }
    // cout<<"ans:"<<ans<<"\n";
    for(int i=1;i<=m;i++)
    {
        for(int j=i+1;j<=m;j++)
        {
            int x=b[i]+b[j];
            res=clone;
            del(b[i]),del(b[j]);
            while(x>1)
            {
                int j=g[x],tot=0;
                while(!(x%prime[j]))x/=prime[j],tot++;
                // cout<<prime[j]<<" "<<tot<<" "<<p[j][0]<<"\n";
                if(tot>p[j][0])res=1ll*res*qpow(prime[j],tot-p[j][0])%mod;
            }
            insert(b[i]),insert(b[j]);
            ans=adj(ans+2ll*c[i]*c[j]%mod*b[i]%mod*b[j]%mod*res%mod);
            // cout<<"done:"<<i<<" "<<j<<" "<<b[i]<<" "<<b[j]<<":"<<res<<" "<<2ll*c[i]*c[j]%mod*res%mod<<"\n";
        }
    }
    printf("%d\n",ans);
}

int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    prework(N-10);
    read(T);
    while(T--)solve();
    return 0;
}