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

所谓权值，就是那一坨排列的生成群的大小。发现如果不是

5

而是

k

显然不是很可做，合理猜测

S_5

的子群数量比较少，随机

100000

次之后发现好像只有

156

个。

得到

156

个子群之后是显然的，枚举每一个把属于子群的排列对应的边连上，看一下

s,t

是否连通即可。

再说一下怎么随出来

156

个子群。首先子群生成元个数

\leq 5

，所以你只需要随机一个

\leq 5

大小的子集即可，然后每次把所有当前元素的复合再扔进去直到不增即可。

给一下生成子群的代码：

CPP

#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;
}

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

文章操作

相关推荐

评论

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