P14310 【MX-S8-T3】图排列 题解

· · 题解

所谓权值，就是那一坨排列的生成群的大小。发现如果不是 5 而是 k 显然不是很可做，合理猜测 S_5 的子群数量比较少，随机 100000 次之后发现好像只有 156 个。

得到 156 个子群之后是显然的，枚举每一个把属于子群的排列对应的边连上，看一下 s,t 是否连通即可。

再说一下怎么随出来 156 个子群。首先子群生成元个数 \leq 5，所以你只需要随机一个 \leq 5 大小的子集即可，然后每次把所有当前元素的复合再扔进去直到不增即可。

给一下生成子群的代码：

#pragma GCC optimize("O2,O3,Ofast,inline,unroll-loops")
#include <bits/stdc++.h>
#define il inline
#define B __int128
using namespace std;
il int pc(B x){
    int ret=0;
    while(x) ret+=(x&1),x>>=1;
    return ret;
}
void write(B x){
    if(x>9) write(x/10);
    putchar(x%10+48);
}
il void print(B x,char c){write(x),putchar(c);}
typedef long long ll;
il int read(){
    int x=0,c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-48,c=getchar();
    return x;
}
mt19937 rnd(time(0));
const int N=1e6+5,K=10005,M=121;
int T,n,a[M][M],b[M][6],P[M],Q[M],R[M],fac[6]={1,1,2,6,24,120};
int USE[M];
il int getid(int a[]){
    int ret=1,x=0;for(int i=1;i<=5;++i) USE[i]=0;
    for(int i=1;i<=5;++i){
        x=0;for(int j=1;j<a[i];++j) x+=1-USE[j];
        ret+=x*fac[5-i],USE[a[i]]=1;
    }
    return ret;
}
il int calc(int x,int y){
    for(int i=1;i<=5;++i) P[i]=b[x][i],Q[i]=b[y][i];
    for(int i=1;i<=5;++i) R[i]=P[Q[i]];
    return getid(R);
}
map<B,int> mp;
int vis[M],cnt;
int group[K][M],tot;
il void calc(int n){
    vector<int> f;int x,y,z,u,v,w;
    for(int i=1;i<=120;++i) vis[i]=0;
    for(int i=1;i<=n;++i) if(!vis[P[i]]) vis[P[i]]=1,f.push_back(P[i]);
    while(1){
        int len=f.size();w=0;
        for(int i=0;i<len;++i) for(int j=0;j<len;++j) {x=f[i],y=f[j],z=a[x][y];if(!vis[z]) vis[z]=1,f.push_back(z),w=1;}
        if(!w) break;
    }

    B s=0,t=1;for(int i=1;i<=120;++i){if(vis[i]) s+=t;t*=B(2);}
    if(!mp.count(s)){
        mp[s]=1,++tot;
        int LEN=f.size();
        printf("{");
        for(int i=0;i<f.size()-1;++i) printf("%d,",f[i]);printf("%d},\n",f[f.size()-1]);
        for(int i=1;i<=120;++i) group[tot][i]=vis[i];
    }
}
il void INIT(){
    int n=5;
    for(int i=1;i<=n;++i) P[i]=i;
    do{
        ++cnt;for(int i=1;i<=n;++i) b[cnt][i]=P[i];
    }while(next_permutation(P+1,P+1+n));
    for(int i=1;i<=cnt;++i) for(int j=1;j<=cnt;++j){
        a[i][j]=calc(i,j);
    }
    for(int i=1;i<=cnt;++i) P[i]=i;
    for(int TT=1;TT<=300000;++TT){
        shuffle(P+2,P+2+cnt,rnd);
        int len=rnd()%5+1;
        calc(len);
    }
    calc(120);
}
int x,y,z,u,v,w;
int main(){
    freopen("test.out","w",stdout);
    INIT();
    return 0;
}