这个标题格式我才看出来它的优越性，如果用「AHOI2022 排列 题解」这种写法会感觉「AHOI2022」「排列」「题解」是并列地位的，比较奇怪，我目前就想到这一种解决方案，也就是 APJ 的那种标题格式 .
首先 \(f(i,j)\neq 0\) 当且仅当 \(a_i,a_j\) 在同一个置换环中 .
然后 \(v(p)\) 就是 \(p\) 所有置换环长度的 lcm，交换 \(a_i,a_j\) 相当于合并两个置换环，可以手玩一下看出来 .
对于环长 \(\{c_k\}\) 满足关系 \(\displaystyle\sum_{i=1}^kc_i\le n\)，于是本质不同的 \(c_i\) 只有 \(O(\sqrt n)\) 种，可以暴力枚举两种 \(c_i\) .
首先处理初始答案，然后每次合并 \(c_i,c_j\) 对 \(c_i,c_j,c_i+c_j\) 分解质因数然后重新计算贡献即可 .
时间复杂度 \(\Theta(n\log n)\) .
const int N = 5e5 + 123, P = 1e9 + 7;
int n, p[N], inv[N], cc[N];
bool nsp[N], vis[N];
vector<pii> fac[N];
multiset<int> cycc[N];
vector<int> prime, cyc;
inline void init(int n)
{
inv[1] = 1;
for (int i=2; i<=n; i++) inv[i] = 1ll * (P - P/i) * inv[P % i] % P;
for (int i=2; i<=n; i++)
{
if (nsp[i]) continue;
prime.emplace_back(i);
for (int j=i; j<=n; j+=i){nsp[j] = true; fac[j].emplace_back(make_pair(i, i));}
for (int j=i; j<=n/i; j*=i)
for (int k=j*i; k<=n; k+=j*i){fac[k].pop_back(); fac[k].emplace_back(make_pair(i, j * i));}
}
}
int main()
{
int T; scanf("%d", &T); init(5e5);
while (T--)
{
scanf("%d", &n); int ans = 0, all = 1; cyc.clear(); cyc.emplace_back(-1);
for (int x : prime)
{
if (x > n) break;
cycc[x].clear();
}
for (int i=1; i<=n; i++){vis[i] = false; cc[i] = 0;} //
for (int i=1; i<=n; i++) scanf("%d", p+i);
for (int i=1; i<=n; i++)
if (!vis[i])
{
int cycle = 0;
for (int j=i; !vis[j]; j=p[j]){++cycle; vis[j] = true;}
++cc[cycle];
}
for (int i=1; i<=n; i++)
if (cc[i])
{
cyc.emplace_back(i);
for (int _=1; _<=cc[i]; _++)
for (pii e : fac[i]) cycc[e.first].insert(e.second);
}
for (int x : prime)
{
if (x > n) break;
cycc[x].insert(1);
}
for (int x : prime)
{
if (x > n) break;
all = 1ll * all * *cycc[x].rbegin() % P;
}
int m = cyc.size() - 1;
for (int i=1; i<=m; i++)
for (int j=i; j<=m; j++)
{
if ((i == j) && (cc[cyc[i]] == 1)) continue;
int now = all, val;
if (i == j) val = 1ll * cc[cyc[i]] * (cc[cyc[i]] - 1) % P;
else val = 2ll * cc[cyc[i]] * cc[cyc[j]] % P;
auto add = [&](int c, int v)
{
for (pii d : fac[c])
{
int p = d.first, e = d.second;
now = 1ll * now * inv[*cycc[p].rbegin()] % P;
if (v == 1) cycc[p].insert(e);
else cycc[p].erase(cycc[p].find(e));
now = 1ll * now * *cycc[p].rbegin() % P;
}
};
add(cyc[i] + cyc[j], 1); add(cyc[i], -1); add(cyc[j], -1);
(ans += 1ll * cyc[i] * cyc[j] % P * val % P * now % P) %= P;
add(cyc[i] + cyc[j], -1); add(cyc[i], 1); add(cyc[j], 1);
}
printf("%d\n", ans);
}
return 0;
}
代码大概是仿的 RSY 的 .
标签：排列,int,AHOI2022,break,解题,题解,cycc From： https://www.cnblogs.com/CDOI-24374/p/17133196.html