首页 > 其他分享 >浅谈高维前缀和

浅谈高维前缀和

时间:2024-09-10 15:36:26浏览次数:13  
标签:浅谈 int 复杂度 一维 维度 高维 前缀

之前做了一道高维前缀和题做着做着忘掉怎么写了,遂记一发。

你说的对,但是我谈的真的很浅。

铺垫

回忆一下我们求前缀和是怎么求的。

一维前缀和:

for(int i=1;i<=n;i++){
	s[i]=s[i-1]+a[i];
}

没有任何问题对吧。

而求二维前缀和时,我们通常会使用如下方法求前缀和(如果不是当我没说):

for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
	}
}

本质上是在做一个容斥。

三维前缀和的式子更长:

for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		for(int k=1;k<=n;k++){
			s[i][j][k]=s[i-1][j][k]+s[i][j-1][k]+s[i][j][k-1]-s[i-1][j-1][k]-s[i-1][j][k-1]-s[i][j-1][k-1]+s[i-1][j-1][k-1]+a[i][j][k];
		}
	}
}

如果维度接着升高,那么这种常规方法我们就要枚举子集做容斥,时间复杂度来到了 \(O(n^w2^w)\)。

我们考虑另一种方法:

先对于每一维,求出仅考虑这一维上的前缀和;接着考虑另一维,再求出仅考虑这一维上的前缀和,写成代码是这样子的(以二维前缀和为例):

for(int i=1;i<=n;i++)s[i][j]=a[i][j];
for(int i=2;i<=n;i++)for(int j=1;j<=n;j++)s[i][j]+=s[i-1][j];
for(int i=1;i<=n;i++)for(int j=2;j<=n;j++)s[i][j]+=s[i][j-1];

关于正确性,我选择从 https://zhuanlan.zhihu.com/p/651143987 嫖一个图过来:

于是时间复杂度降到了 \(O(n^ww)\),这就是高维前缀和的核心思路。

问题引入

给定 \(2^n\) 个数 \(a_i\),从 \(0\) 开始标号。令 \(f_S\) 为 \(\sum_{T\operatorname{or} S=S}a_T\),对 \(S=0\sim 2^n-1\) 求 \(f_S\)。

\(n\le 20\)。

分析

显然有一个 \(O(4^n)\) 的暴力。

把 \(S\) 的每一个二进制位记为一个维度,那么 \(f_S\) 就相当于对所有的这 \(n\) 维做高维前缀和,只不过每一维只有 0/1 两种取值。

代码实现:

for(int S=0;S<(1<<n);S++)
	for(int i=0;i<n;i++)
		if((S>>i)&1)
			f[S]+=f[S^(1<<i)];

时间复杂度 \(O(2^nn)\)。

例子:狄利克雷前缀和

题面:https://www.luogu.com.cn/problem/P5495

对所有 \(x=1\sim n\) 求 \(f_x=\sum_{y|x} a_y\)。

\(n\le 2\times10^7\)。

分析

将数 \(x\) 唯一分解成 \(x=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\) 的形式,把每个质因数视为一个维度,对所有维度做一遍高维前缀和。由于每一维的取值是在 \(0\) 到 \(\dfrac{n}{p}\) 之间的,时间复杂度 \(\sum_{p\in prime}\dfrac{n}{p}=O(n\log \log n)\)。

代码实现:

for(int i=2;i<=n;i++){
	if(!flag[i]){//flag[i]为质数标记 
		for(int j=1;i*j<=n;++j){
			flag[i*j]=1;
			a[i*j]+=a[j];
		}
	}
}

标签:浅谈,int,复杂度,一维,维度,高维,前缀
From: https://www.cnblogs.com/dcytrl/p/18406487

相关文章

  • 浅谈人工智能之Python调用AutoGen Studio SDK
    浅谈人工智能之Python调用AutoGenStudioSDK引言在之前的文档中我们讲解了如何搭建AutoGenStudio环境以及基于AutoGenStudio构建AIAgent并且进行执行。今天我们介绍如何通过Python调用AutoGenStudio提供的SDK来运行workflow,即AIAgent。实例说明第一步:我们使用命......
  • 安全运营之浅谈SIEM告警疲劳
    闲谈:     刚开始学习SIEM、态势感知这类产品的时,翻阅老外们的文章总是谈什么真阳性,假阳性告警、告警疲劳,当时在国内资料中没找到很合理的解释,慢慢就淡忘这件事了。随着慢慢深入工作,感觉大概理解了这些概念并且有了一些新的领悟。心血来潮写了这篇文章,想给刚接触SIEM......
  • 信息学奥赛初赛天天练-87-NOIP2014普及组-完善程序-矩阵、子矩阵、最大子矩阵和、前缀
    1完善程序最大子矩阵和给出m行n列的整数矩阵,求最大的子矩阵和(子矩阵不能为空)。输入第一行包含两个整数m和n,即矩阵的行数和列数。之后m行,每行n个整数,描述整个矩阵。程序最终输出最大的子矩阵和。(最后一空4分,其余3分,共16分)比如在如下这个矩阵中:440-2-7......
  • 【转】数据模型——从D模型到C/C'模型的浅谈
    数据模型——从D模型到C/C'模型的浅谈原文链接:https://zhuanlan.zhihu.com/p/521380989DSColloquium在DA和ML中寻找life的wisdom(真香~)​关注 15人赞同了该文章一、引言在日常企业运营和发展过程中,总会遇到这么一个情景:已有的业务系统的设计与实施......
  • 浅谈:CDN下真实IP的暴露
    免责声明:本文仅做分享! 目录CDN简介:国内常见CDN:国外常见CDN:判断CDN存在?在线ping检测:nslookup:寻找真实IP---->1-DNS历史解析纪录2-子域名查询1.在线平台查询2.工具爆破3.搜索引擎3-网站邮件头信息4-SSL证书查找真实IP(1)浏览器查找(2)openssl查看(3)......
  • 浅谈会话技术:Cookie和Session
    1前言1.1内容提要理解使用会话技术的原因理解客户端技术和服务器技术之间的区别掌握Cookie的设置(构造),熟悉Cookie的获取,能够通过浏览器查看Cookie信息理解Session维护的机制,能够分析Session的失效原因熟悉使用Session存储和获取信息掌握Cookie和Session的使用场景1.2前......
  • [c++][笔记]浅谈几种排序方式---冒泡排序,选择排序,桶排序
     一、algorithm里的sort函数 #include<cstdio>//数据小的可以用iostream#include<algorithm>//不能忘记算法库,否则会编译失败。usingnamespacestd;intmain(){intn;scanf("%d",&n);inta[n+5]={};for(inti=1;i<=n;i++){......
  • C#一分钟浅谈:LINQ 查询表达式的使用技巧
    在C#开发中,LINQ(LanguageIntegratedQuery)是一项强大的功能,它允许开发者以接近自然语言的方式查询数据集合。LINQ不仅简化了数据操作,还提高了代码的可读性和可维护性。本文将从基础开始,逐步深入探讨LINQ查询表达式的使用技巧,并通过具体的代码示例帮助理解常见的问题及如何避免错误......
  • Java-IO:浅谈对NIO的认识
    Java-IO:简述常见的IO模型Java-IO:浅谈对IO的认识NIO即NewIO,这个库是在JDK1.4中才引入的。NIO和IO有相同的作用和目的,但实现方式不同,NIO主要用到的是块,所以NIO的效率要比IO高很多。在JavaAPI中提供了两套NIO,一套是针对标准输入输出NIO,另一套就是网络编程NIO。一、NIO......
  • 天润融通解开售后维修的成本枷锁,提高维修服务效率
    如今,企业客户服务在开展业务咨询和售后受理时,主要方式还是通过电话与在线方式进行。这种方式虽然方便,但是对于一些非常紧急的情况还是显得有些不够。比如,虽然现在许多企业APP已经实现了一键咨询和一键报修,但当客服收到问题反馈后,还需要将预约记录转交给维修工程师,之后维修工程师再......