烈阳

Cetana · 2026-05-18 17:44:11 · 题解

upd：

• 26/05/19：修改若干笔误

简要题意

给定 k 个 1\sim n 的置换 p_1,p_2,\cdots,p_k，对于这些置换相互复合生成的置换群 S=<p_1,p_2,\cdots,p_k> ，求 \dfrac{\sum\limits_{q\in S}\sigma(q)}{|S|} 关于一个大质数的模数。

满足 1\le n\le 3000 和 k\le 3000。

若干关键观察

• 由于一些关于置换群的基础知识，我们知道任意一个置换 p 自复合有限次后一定可以得到恒等置换 e 和自身的逆置换 p^{-1}。

• 直接算分子分母是困难的，考虑对每一对满足 1\le i<j\le n 的 i,j 算 q_i>q_j 的概率再累加。

• 对于一对 i,j，记 A_{i,j}=\{(q_i,q_j)|q\in S\}，那么任意 A 中元素在最终结果里出现的概率是均等的。

  考虑简单证明一下：

  对于每一对 (i,j) 向 (p_{x,i},p_{x,j})(x=\overline{1,2,\dots,k}) 连一条边权为 p_x 的单向边，同时我们也可以连一条 (p_{x,i},p_{x,j}) 向 (i,j) 边权为 p_x^{-1} 的边。

  考虑对于每一个连通块指定一个根 (a,b)，我们找出一棵以 (a,b) 为根的 dfs 树，对于连通块中任意一个点 (x,y)，将 (a,b) 到 (x,y) 的树上路径上的置换依次复合得到一个可以将 (a,b) 置换到 x,y 的置换 l_{x,y}，同理得到 l_{x,y}^{-1}。那么对于任意两对 (x,y),(u,v)，若存在一个 q\in S,q\circ(a,b)=(x,y) 那么也将存在 q'=l_{u,v}\circ l_{x,y}^{-1}\circ q 满足 q'\circ(a,b)=(x,y)。

  然后易得对任意 (x,y),(u,v)，S 中将 (a,b) 置换到 (x,y) 的置换与将 (a,b) 置换到 (u,v) 的置换是一一对应的。

  即每一个连通块中所有元素最终是等概率出现的。

  事实上，不仅限于二元组，上述证明对任意元组均成立。

• 然后我们有了一个 O(n^2k) 的做法：用 p_1,p_2\cdots,p_k 依次更新 n^2 个点的连通块关系。最终若一个集合中有 A 个 i<j 的 (i,j) 和 B 个 i>j 的 (i,j)，则产生 \dfrac{AB}{A+B} 的贡献。

考虑优化

• 注意到我们只关心集合 O=\{(i,j)|1\le i,j\le n\wedge i\neq j\} 在 S 作用下的所有轨道，而不关心 S 具体的结构是什么样子。

• 考虑发扬人类智慧。

• 我们称一次采样为随机取一个 \{p_1,p_2,\cdots,p_k\} 的子集再以随机顺序（依次也可以）复合起来得到置换 q 更新一次连通块信息。

  我们宣称 O(\log n) 次采样即可完全刻画出 O 的所有轨道（实验发现 30 次够用）。

  所以我们把时间复杂度优化到了 O(n^2\log n)。

考虑简要分析（口胡）正确性

• 假设在若干次采样后目前的连通块信息 C 中仍存在需要合并但没有合并的连通块（C 若干连通块的集合）。

  考虑目前这一次采样，因为 C 中存在需要合并的连通块，则一定存在若干可以使得连通块信息改变的置换，记其中第一个为 p_l。考虑我们的置换 q，在考虑到 l 之前，q 一定不会更新 C 的信息；在考虑完 p_l 时，我们有 \frac12 的概率让 q 更新连通块。

  现在我们考虑归纳证明在考虑完 l 之后的每一个置换后仍有至少 \frac12 的概率更新连通块信息：

  如果某个 k>l 满足在考虑完 p_{k-1} 后我们仍有至少 \frac12 的概率更新连通块信息，我们讨论 p_k 本身能不能更新连通块信息：

  • 若不能，则表明 p_k 只会将元素在连通块内置换，即无法改变 q 能否更新连通块信息。
  • 若能，记 Pr 为原本 q 能更新连通块信息的概率，则 Pr'\ge \frac12 Pr+\frac12(1-Pr)=\frac12。

  得证。

• 因此对于 C 中每一个还需要被合并的集合 \mu，每次采样有至少 \frac12 的概率与另一个集合合并，即我们每次采样期望可以将还需要合并的集合的数量缩小到原来的 \frac34，期望 \log_{\frac43}n^2 次采样后即可完整刻画连通块信息。

:::success[Code（略去缺省源）]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
struct Mod{
    ll v,p;
    constexpr Mod(int x){
        p=x;
        v=((__int128)(1)<<64)/p;
    }
    inline int operator()(ll x)const{
        return x-((__int128)(x)*v>>64)*p;
    }
};
const Mod bar(mod);
int n,k,ans,tot,id[3005][3005];
vector<int>p[3005];
int fa[9000005],w[9000005],siz[9000005],inv[9000005];
int find(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
void uni(int x,int y){
    x=find(x);y=find(y);
    if(x==y)return;
    if(w[x]>w[y])swap(x,y);
    fa[x]=y;
    w[y]+=w[x];
    siz[y]+=siz[x];
}
mt19937 rd(20260616);
signed main()
{
    read(n,k);
    for(int i=1;i<=k;i++){
        p[i].resize(n+1);
        for(int j=1;j<=n;j++)read(p[i][j]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            id[i][j]=++tot;
            fa[tot]=tot;
            siz[tot]=1;
            w[tot]=(i>j);
        }
    }
    auto upd=[&](vector<int>pr){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int u=id[i][j],v=id[pr[i]][pr[j]];
                uni(u,v);
            }
        }
    };
    int ttt=30;
    while(ttt--){
        shuffle(p+1,p+k+1,rd);
        vector<int>x(n+1),y(n+1);
        for(int i=1;i<=n;i++)x[i]=i;
        for(int i=1;i<=k;i++){
            if(rd()%2){
                for(int j=1;j<=n;j++)y[j]=x[p[i][j]];
                x.swap(y);
            }
        }
        upd(x);
    }
    inv[1]=1;
    for(int i=2;i<=n*n;i++)inv[i]=bar((ll)(mod-mod/i)*inv[mod%i]);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int p=find(id[i][j]);
            ans+=bar((ll)w[p]*inv[siz[p]]);
            ans=ans>=mod?ans-mod:ans;
        }
    }
    print(ans,'\n');
    return 0;
}

:::