首页 > 其他分享 >如何在不能求逆的时候做子集卷积 exp(即便能求逆也比常见方法优雅)

如何在不能求逆的时候做子集卷积 exp(即便能求逆也比常见方法优雅)

时间:2024-07-02 15:32:16浏览次数:1  
标签:求逆 nn 卷积 复杂度 子集 exp 能求

为什么要求逆?正常做子集卷积 exp 的时候递推求 \(G=\exp(F)\) 的系数时要用。

什么情况下不能求逆?模 \(2^{64}\),或者压根不取模。

我们可能会想,算出来肯定除得尽啊,因为组合意义上是不会出现分数的。

并非如此,例如我们可能会尝试算 \(\exp(x)\cdot \exp(2x)\) 的 \([x^3]\) 处的系数乘上 \(3!\) 的结果,乘回来的结果肯定是整数,但运算过程中并不是。

考虑怎么绕开求逆。

对于喜欢组合意义的人:

假设我们对集合幂级数 \(F\) 做子集卷积 exp。

考虑第 \(n\) 个元素选或不选。如果不选,那么我们递归求出只考虑前 \(n-1\) 个元素的子集卷积 exp 的结果,记做 \(G_0\)。

如果选,那么考虑最终选出包含 \(n\) 的集合是哪个,设其为 \(S\),那么我们就是从 \(F\) 中选出一个包含 \(n\) 这个元素的集合 \(S\),再从 \(G_0\) 中选出一个集合 \(T\),贡献到 \(S\cup T\)。

这就是一个简单的子集卷积,可以 \(O(2^nn^2)\) 完成。

而总时间复杂度由递推式 \(T(n)=T(n-1)+O(2^nn^2)\) 计算,可以得到就是 \(O(2^nn^2)\) 的,和原来的复杂度一样,但是好写得多,因为不需要预处理逆元以及推一遍 n^2 求 exp 的式子。

对于喜欢代数推导的人:

原 CF Blog

把集合幂级数视为一个 \(n\) 元截断多项式 \(R(x_1,x_2,\dots,x_n)/(x_1^2,x_2^2,\dots,x_n^2)\)。

那么 \(G=\exp(F)\),\([x_n^0]G=\exp([x_n^0]F)\),\([x_n^1]G=[x_n^0]G[x_n^1]\exp(F)=[x_n^0]G[x_n^1]F\)。

所以我们只用递归求解 \([x_n^0]G\),就可以通过一次子集卷积求出 \([x_n^1]G\),两者拼接得到 \(G\)。

总时间复杂度由递推式 \(T(n)=T(n-1)+O(2^nn^2)\) 计算,可以得到就是 \(O(2^nn^2)\) 的,和原来的复杂度一样,但是好写得多,因为不需要预处理逆元以及推一遍 n^2 求 exp 的式子。

代码实现

这里是两种代码实现测速的地址

不用 vector 的话,简单来说,就一行:

G[0]=1; For(i,0,n-1) Conv(G,F+(1<<i),G+(1<<i),i);

其中 Conv(a,b,c,k) 表示对数组 a 和数组 b 做长为 k 的子集卷积,把结果放到 c 处。

标签:求逆,nn,卷积,复杂度,子集,exp,能求
From: https://www.cnblogs.com/Charlie-Vinnie/p/18279952

相关文章

  • DevExpress WinForms磁贴导航面板 & TileBar组件,让桌面应用触摸更友好!
    界面控件DevExpressWinFormsTileNavPane被设计为位于应用程序窗口的顶部(就像Ribbon一样),可以被认为是Windows桌面应用程序中传统导航元素的触摸友好版本。P.S:DevExpressWinForms拥有180+组件和UI库,能为WindowsForms平台创建具有影响力的业务解决方案。DevExpressWinForms能......
  • explain解析
    1.idselect的查询顺序,如果ID相同则按从上到下。2.selecttype区分查询是简单还是复杂查询1)simple:简单音询。查询不包含子音询和unionexplainselect*fromfilmwhereid=2:2)primary:复杂查询中最外层的select3)subquery:包含在select中的子查询(不在from子句中......
  • [论文阅读] Calligraphy Font Generation via Explicitly Modeling Location-Aware Gl
    Pretitle:CalligraphyFontGenerationviaExplicitlyModelingLocation-AwareGlyphComponentDeformationssource:TMM2023paper:https://ieeexplore.ieee.org/document/10356848code:None关键词:generativeadversarialnetworks,imageprocessing,imagesynth......
  • 如何使用Express.js创建一个基本的路由?
    在现代Web开发或面试过程中,Express.js成为了必不可少的一部分。Express.js是Node.js的一个非常受欢迎和强大的框架,而创建路由是这个框架的核心功能之一。在这篇文章中,我们将详细介绍如何使用Express.js创建一个基本的路由,并附上示例代码帮助你理解。什么是路由?路由决定了......
  • K8S学习教程(一):使用PetaExpress云服务器安装Minikube 集群
    什么是MinikubeMinikube是一款工具,主要用于在本地运行Kubernetes集群。Kubernetes开源的平台,用于自动化容器化应用的部署、扩展和管理,而Minikube使得开发人员能够在本地机器上轻松创建一个单节点的Kubernetes集群,从而方便开发、测试和学习Kubernetes。我们看下......
  • uni-app编译错误:“hasInjectionContext“ is not exported by “node_modules/.pnpm/p
    1.问题背景当我们接手一个新的uni-app项目(最头疼了x_x),可能会想到删掉node_modules和pnpm-lock.yaml后,执行npminstall或npminstall重新安装依赖包,然后执行pnpmdev:mp-weixin编译,但可能会遇到如下错误:"hasInjectionContext"isnotexportedby"node_modul......
  • 使用explain优化慢查询的业务场景分析
    问:你最害怕的事情是什么?答:搓澡问:为什么?答:因为有些人一旦错过,就不在了Explain这个词在不同的上下文中有不同的含义。在数据库查询优化的上下文中,"EXPLAIN"是一个常用的SQL命令,用于显示SQL查询的执行计划。执行计划是数据库如何执行查询的一个详细描述,包括它将使用哪......
  • 界面组件DevExpress WPF v24.1 - 增强的可访问性 & UI自动化
    DevExpressWPF拥有120+个控件和库,将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpressWPF能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。DevExpressWPF控件日前正式发布了今年一个重大版......
  • Create Detailed Documentation and Export to DOCX
    CreateDetailedDocumentationandExporttoDOCXDr.Explainv6.8addstheabilitytoexporttotheMicrosoftWordDOCXformat,providinggreaterflexibilityfordevelopersandusersalike.Dr.ExplainbyIndigoByteSystemsisasophisticatedso......
  • 【译】VisualStudio.Extensibility 17.10:用 Diagnostics Explorer 调试您的扩展
    想象一下,创建的扩展比以往任何时候都运行得更快、更流畅!如果您最近还没有跟上,我们一直在努力改进VisualStudio.ExtensibilitySDK。VisualStudio.Extensibility帮助您构建在主IDE进程之外运行的扩展,以提高性能和可靠性。它还提供了一个时尚而直观的基于.NET8的API......