首页 > 其他分享 >生成子群阶数问题

生成子群阶数问题

时间:2024-05-20 22:51:15浏览次数:20  
标签:rt 生成元 int 置换 元组 阶数 子群 生成 取值

之前看到 grass8cow 博客中关于 Grupa Permutacji 这道题做法的简略记述后一直感觉这个题是究极神秘题。APIO 听了 Kubic 的讲课(当时讲的是 LOJ177 生成子群阶数)后终于算是懂了一点了。

众所周知,所有有限群同构于一个置换群的子群。当我们拿着一堆置换,然后再复合来复合去,所有可能得到的结果自然生成了一个群。grupa 这个题研究了这个群的平均逆序对个数,而 LOJ177 研究了这个群的大小。以前我一直认为这种东西很难做,出乎意料的是这两个问题都可以做到 \(O(\text{poly}(n))\)。

解决这两个问题的第一个共同关键是在于生成子群的“均匀性”。我们这样描述这个性质:对于所有置换的第 \(i\) 位 \(p_i\) 来说,假设 \(p_i\) 有 \(k\) 种不同的取值 \(a_1,a_2,\dots,a_k\),则 \(p_i\) 取到这 \(k\) 种取值中的每种取值的方案数都是一样的。这个结论不仅对于单个 \(p_i\) 成立,对于多个 \(p_i\) 取值集合笛卡尔积形成的多元组来说也是成立的。

比如说,对于 grupa 这个题我们研究逆序对,所以对于一个下标二元组 \((i,j)\),生成子群中所有元素的取值二元组 \((p_i,p_j)\) 取到每种可能的取值的概率相等。逆序对就是 \(i<j,p_i>p_j\) 的元组。所以我们直接对于每一个生成元排列的每一个二元组连双向边 \((i,j)\leftrightarrow (p_i,p_j)\),然后统计每个连通块中满足 \(i<j\) 和 \(i>j\) 的元组数,分别设为 \(a,b\),则从每个 \(i<j\) 的元组出发到 \(i>j\) 的元组的概率是 \(\frac{b}{a+b}\),对答案的总贡献就是 \(\frac{ab}{a+b}\)。我们得到了一个 \(O(n^3)\) 的做法。

如何说明这种“均匀性”呢?我们考虑建图分析。对于每个生成元置换 \(s\) 中若干个固定的下标形成的多元组 \((\alpha_1,\alpha_2,\dots \alpha_m)\) 向 \((s_{\alpha_1},s_{\alpha_2},\dots s_{\alpha_m})\) 连边,再在这条边上写上 \(s\) 作为边权。

由于置换群不断的复合自己总会走回自己,所以说我们同时可以连一条反向边,再写上 \(s^{-1}\) 作为边权,所以我们可以直接将这张图当成无向图处理。不过就我们下面的分析来说有向图也没影响。

这样,你从任意元组 \(rt\) 开始 dfs,能 dfs 到的所有元组就是它能取到的所有取值元组。而你取任意一条路径 \(rt\to x\),其上的所有边依次复合就得到了取到这个取值元组的一个置换。

我们不妨取一个以 \(rt\) 为根的 dfs 生成树。这样对于每一个 \(rt\to x\) 就钦定了唯一一条路径,那么对于一个取值元组取到 \(x\) 的方案,我们这条路径上的置换一一逆复合回去,由于置换群逆元存在且唯一,那么每一个取值元组取到 \(x\) 的置换一一对应着一个取值元组取到 \(rt\) 的置换。均匀性得证。

解决这两个问题第二个共同的关键在于如何削减生成元集合的大小,也就是说找到另一组生成元集合使得它们跟原生成元集合生成的群同构。如果你无聊中翻过 OI-wiki 中一些较为冷门的页面,你可能会知道 schreier-sims 算法 给出了一个这个问题的确定性做法。我没有认真看过这个算法 QwQ,只大致看过 Kubic APIO 讲义里的东西,但是更适合 OI 宝宝体质的做法是:随机选取一个生成元的子集,以任意顺序复合起来,重复足够多次之后将有大概率得到一些能够生成原来的群的置换。

所以对于 grupa 这个题我们选取 \(O(\log)\) 个子集后就得到了一个 \(O(n^2\log n)\) 的做法?!?!

// ...
int n,k;
int a[N][N];
int p[N],q[N];
inline int id(int x,int y){return (x-1)*n+y;}
int f[N*N],inv[N*N];
int ca[N*N],cb[N*N];
int rt(int x){
	if(f[x]==x) return x;
	return f[x]=rt(f[x]);
}
int main(){
	n=read();k=read();
	for(int i=1;i<=k;++i)
		for(int j=1;j<=n;++j) a[i][j]=read();
	for(int i=1;i<=n*n;++i) f[i]=i;
	for(int it=0;it<L;++it){
		for(int t=1;t<=n;++t) p[t]=t;
		for(int i=1;i<=k;++i)
			if(rng()&1){
				for(int t=1;t<=n;++t) q[p[t]]=a[i][t];
				for(int t=1;t<=n;++t) p[t]=q[t];
			}
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j){
				if(i==j) continue;
				f[rt(id(i,j))]=rt(id(p[i],p[j]));
			}
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			if(i==j) continue;
			if(i<j) ++ca[rt(id(i,j))];
			else ++cb[rt(id(i,j))];
		}
	inv[1]=1;
	for(int i=2;i<=n*n;++i) inv[i]=(ll)inv[P%i]*(P-P/i)%P;
	int res=0;
	for(int i=1;i<=n*n;++i)
		if(f[i]==i&&ca[i]&&cb[i]) res=(res+(ll)ca[i]*cb[i]%P*inv[ca[i]+cb[i]])%P;
	printf("%d\n",res);
	return 0;
}

再考虑 LOJ177 这个题。我们统计有多少种置换,不妨先统计 \(p_n\) 有多少种取值,然后再统计强制 \(p_n=n\) 的方案数,两者相乘就是答案。

前者方法我们已经熟知,后者可以这样考虑:之前我们建出来的每一个经过 \(n\) 的环都是一个 \(p_n=n\) 的方案,我们有一组可以生成它们的生成元:对于每一条边 \((u,v)\),取 \(n\to u,u\to v,v\to n\) 这个环。对于这些生成元我们缩减它的集合大小至 \(O(n)\),就可以递归到一个 \(n-1\) 的问题了!我们在 \(O(n^5)\) 的时间内解决了 LOJ177。

// ...
struct perm{
	int p[N];
	void init(){
		for(int i=1;i<=n;++i) p[i]=i;
	}
	friend perm operator+(const perm a,const perm b){
		perm c;
		for(int i=1;i<=n;++i) c.p[i]=b.p[a.p[i]];
		return c;
	}
	perm inv(){
		perm x;
		for(int i=1;i<=n;++i) x.p[p[i]]=i;
		return x;
	}
}a[N],b[N],path[N<<1];
vector<pii> vec[N];
ll res[10];int len;
bool vis[N];
void dfs(int u,perm cur){
	path[u]=cur;
	vis[u]=1;++num;
	for(auto [v,w]:vec[u]){
		if(vis[v]) continue;
		dfs(v,cur+a[w]);
	}
}
void iter(){
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j) vec[j].emplace_back(a[i].p[j],i);
	perm Init;
	Init.init();
	dfs(n,Init);
	for(int i=1;i<=n;++i) path[i+n]=path[i].inv(),vec[i].clear();
	for(int it=1;it<=B;++it){
		b[it].init();
		for(int i=1;i<=m;++i)
			for(int j=1;j<=n;++j)
				if(vis[j]&&(rng()&1)) b[it]=b[it]+path[j]+a[i]+path[a[i].p[j]+n];
	}
	for(int i=1;i<=n;++i) vis[i]=0;
	m=B;
	for(int i=1;i<=m;++i) a[i]=b[i];
	--n;
	ll carry=0;
	for(int i=0;i<=len;++i){
		res[i]*=num;res[i]+=carry;
		carry=res[i]/T;res[i]%=T;
	}
	if(carry) res[++len]=carry;
	num=0;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j) a[i].p[j]=read();
	res[len=0]=1;
	while(n) iter();
	printf("%lld",res[len]);
	for(int i=len-1;~i;--i) printf("%016lld",res[i]);
	putchar('\n');
	return 0;
}

标签:rt,生成元,int,置换,元组,阶数,子群,生成,取值
From: https://www.cnblogs.com/yyyyxh/p/18202915/groupsize

相关文章

  • NumPy 数组排序、过滤与随机数生成详解
    NumPy数组排序排序数组排序数组意味着将元素按特定顺序排列。顺序可以是数字大小、字母顺序、升序或降序等。NumPy的ndarray对象提供了一个名为sort()的函数,用于对数组进行排序。示例:importnumpyasnparr=np.array([3,2,0,1])print(np.sort(arr))输出:[0......
  • Liunx下通过netcore接口生成前端图片的问题。
    用netcore来生成前端微信Native支付的二维码。1、首先CentOS7.0要安装libgdiplus,命令如下:yuminstalllibgdiplus-devel,然后重启netcore服务。//这个地方要注意,网上有不少例子的下载命令是错的,有的时候安装不上。2、Vs代码使用QRCoder库,代码如下publicstaticMemoryStream......
  • axis2生成wsdl回执参数首字母大小写问题
    在跟局方对接接口的时候,局方回执我的wsdl接口,发现收不到同步回执,怀疑问题为回执参数首字母小写导致  代码中的参数对象首字母确实是大写,但生成的wsdl文件确变成了小写,目前是用axis2生成的参考:https://bbs.csdn.net/topics/390457284发现了变为小写的原因,选择使用xFire......
  • Amazon Q Developer 实战:从新代码生成到遗留代码优化(上)
    本文将探索如何在VisualStudioCode这个开发者常用的一种集成编程环境(IDE)中,使用AmazonQDeveloper列出指定区域的AmazonS3存储桶的示例代码实现。我们将从在AmazonQDeveloperAgent的协助下,从生成新代码开始,到将生成的新代码与现有的低效“遗留”旧代码进行性能对比;......
  • 【.NET项目分享】免费开源的静态博客生成工具EasyBlog,5分钟拥有自己的博客
    EasyBlog说明本博客系统通过构建工具生成纯静态的博客网站,借助GitHubPages,你可以在5分钟内免费拥有个人博客。它具有以下特点生成纯静态网站,访问速度极快使用markdown格式来编写博客内容基于git代码管理来存储你的博客使用CI工具来自动化部署你的博客站点效果展示:NilTo......
  • 人工智能帮你一键生成完美架构图
    简介架构图通过图形化的表达方式,用于呈现系统、软件的结构、组件、关系和交互方式。一个明确的架构图可以更好地辅助业务分析、技术架构分析的工作。架构图的设计是一个有难度的任务,设计者必须要对业务、相关技术栈都非常清晰才能设计出来符合需求的架构图。实践演练有明确的......
  • Uni-app 之IOS生成Universal Link(通用链接)
    一、文档https://uniapp.dcloud.net.cn/api/plugins/universal-links.html#%E8%83%8C%E6%99%AF%E4%BB%8B%E7%BB%8D二、配置1、登录苹果开发者中心找到对应的APPID,配置AssociatedDomains,如下: 2、创建apple-app-site-association文件(没有后缀){"applinks":{......
  • 开源低代码框架 ReZero API 正式版本发布 ,界面操作直接生成API
    一、ReZero简介ReZero是一款.NET中间件:全网唯一界面操作就能生成API, 可以集成到任何.NET6+API项目,无破坏性,也可让非.NET用户使用exe文件免费开源:MIT最宽松协议,一直从事开源事业十年,一直坚持开源1.1纯ReZero开发适合.NetCore零基础用户,大大简化了.NetCore开发门......
  • 终于搞懂了!原来 Vue 3 的 generate 是这样生成 render 函数的
    前言在之前的面试官:来说说vue3是怎么处理内置的v-for、v-model等指令?文章中讲了transform阶段处理完v-for、v-model等指令后,会生成一棵javascriptAST抽象语法树。这篇文章我们来接着讲generate阶段是如何根据这棵javascriptAST抽象语法树生成render函数字符串的,本文中使用的v......
  • ue5生成vs工程报错-msvc版本太旧
    ue生成VS工程报错右键-uproject,GeneratingVisualStudioprojectfiles,报错信息如下:就是我安装的msvc版本太旧RunningC:/ProgramFiles/EpicGames/UE_5.3/Engine/Build/BatchFiles/Build.bat-projectfiles-project="D:/ue/myue/myue.uproject"-game-rocket-progres......