首页 > 其他分享 >更^{2+eps}炫酷的反演魔术

更^{2+eps}炫酷的反演魔术

时间:2024-07-03 19:59:02浏览次数:21  
标签:big sum eps 反演 炫酷 mathcal 集合 rm col

考虑将二项式反演的符号化方法扩展到斯特林反演上。

染色问题
现有一排 \(n\) 个格子,每个格子皆可涂成 \(c\) 种颜色之一。
给定集合 \(W\),定义一个染色合法当且仅当:对于任意格子,记和它颜色相同的格子有 \(x\) 个(包括自身),必有 \(x\in W\)。
求有多少合法的染色方案。

可以直接用 EGF 推导:单个颜色的 EGF 为 \(F(z)=1+\sum\limits_{k\in W}\frac{x^k}{k!}\),答案是 \(\big[\frac{x^n}{n!}\big]F^c(z)\)。

接下来展示斯特林容斥的推理方法。

记 \(\mathcal S\) 为带染色的集合划分,且集合大小在 \(W\) 中。

记 \(\mathcal S^{\rm col}\) 为带染色的集合划分,满足集合的颜色各不相同(缤纷),且集合大小在 \(W\) 中。\(|\mathcal S^{\rm col}_n|\) 即为答案。

记 \(\mathcal S_0\) 为有标号集合,集合大小在 \(W\) 中。(无色透明)有 \(S_0(z)=\sum_{k\in W}\frac{x^k}{k!}\)。

记 \(\mathcal D\) 为带染色的有标号无序集。

记 \(\mathcal D^{\rm col}\) 为带染色的有标号无序集,且元素的颜色各不相同(缤纷)。

根据“子结构构造”的组合意义,用有标号非空集合(无色透明)替换 \(\mathcal D\) 的元素(并继承其颜色),有

\[\begin{aligned} \mathcal S&=\mathcal D\boxtimes \mathcal S_0\\ \mathcal S^{\rm col}&=\mathcal D^{\rm col}\boxtimes \mathcal S_0 \end{aligned} \]

观察 \(\mathcal D\) 是如何从 \(\mathcal D^{\rm col}\) 生成的,根据二项式反演的经验,我们最好让任意一个 \(d'\in\mathcal D\) 对应到唯一一个 \(d\in D^{\rm col}\),然后再考虑反射。

对任意一个 \(d'\in\mathcal D\),将同色的元素合并,就满足各个元素颜色不同。反之,对任意一个 \(d\in \mathcal D\),可以将其中的每个元素扩增若干倍(每个元素换成任意大的纯色非空集合),这样能得到 \(\mathcal D\) 中的所有元素。

具体地,设 \(\mathcal D_0\) 为有标号非空无序集合(无色透明)(\(D_0(u)=e^u-1\)),根据“子结构构造”

\[\mathcal D=\mathcal D^{\rm col}\boxtimes \mathcal D_0 \]

翻译为 EGF,得

\[\begin{aligned} D(u)&=\sum_{k=0}^{+\infty}\dfrac{c^ku^k}{k!}=e^{cu}\\ D(u)&=D^{\rm col}(D_0(u))=D^{\rm col}(e^u-1)\\ D^{\rm col}(u)&=D(\ln(1+u))=(1+u)^c\\ S(z)&=D(S_0(z))=\big(1+S_0(z)\big)^c\\ \end{aligned} \]

其中 \(e^u-1\) 的复合逆是 \(\ln(1+u)\)。

由于本题的特殊性,其实也可以直接求出 \(D^{\rm col}(u)\)。注意到 \(k\) 个缤纷的有标号元素方案数为 \(c^{\underline k}\),得

\[D^{\rm col}(u)=\sum_{k=0}^{+\infty}\frac{c^{\underline k}x^k}{k!}=\sum_{k=0}^c\binom{c}{k}x^k=(1+u)^c \]

Loj6728 U 群把妹王

现有 \(n\times m\) 个格子,每个格子皆可涂成 \(c\) 种颜色之一。

给定集合 \(W_1,W_2\),定义一个染色合法当且仅当:

  • 对于任意一行,记和它图案相同的行有 \(x\) 个(包括自身),必有 \(x\in W_1\)。
  • 对于任意一列,记和它图案相同的列有 \(x\) 个(包括自身),必有 \(x\in W_2\)。

求有多少合法的染色方案。

这是上一题的扩展版本。

记 \(\mathcal S\) 为:将行列划分,行集合大小在 \(W_1\) 中,列集合大小在 \(W_2\) 中,每个行集合相等,每个列集合相等。

记 \(\mathcal S^{\rm col}\) 为:在 \(\mathcal S\) 的基础上,要求行列的划分均是缤纷的。

记 \(\mathcal D\) 为:一对带染色有标号无序集(分别管理行和列,每个元素管控一个行/列集合)。

记 \(\mathcal D^{\rm col}\) 为:在 \(\mathcal D\) 的基础上,要求行列均是缤纷的。

记 \(\mathcal S_1\) 为有标号行集合,集合大小在 \(W_1\) 中;\(\mathcal S_2\) 为有标号列集合,集合大小在 \(W_2\) 中(均无色透明),则有

\[\begin{aligned} \mathcal S&=\mathcal D\boxtimes(\mathcal S_1,\mathcal S_2)\\ \mathcal S^{\rm col}&=\mathcal D^{\rm col}\boxtimes(\mathcal S_1,\mathcal S_2) \end{aligned} \]

即:将一个行集合换成若干行,一个列集合换成若干列。

设 \(\mathcal D_1\) 为有标号非空无序行集合,\(\mathcal D_2\) 为有标号非空无序列集合(均无色透明),根据“子结构构造”

\[\mathcal D=\mathcal D^{\rm col}\boxtimes(D_1,\mathcal D_2) \]

即:将行列(集合)分别复制若干次。

用 \(u,v\) 表示行列,写出 EGF 得

\[\begin{aligned} S_1(u)&=\sum_{k\in W_1}\frac{u^k}{k!}\\ S_2(v)&=\sum_{k\in W_2}\frac{v^k}{k!}\\ D(u,v)&=\sum_{n=1}^{+\infty}\sum_{m=1}^{+\infty}c^{nm}\dfrac{u^nv^m}{n!m!}\\ D(u,v)&=D^{\rm col}(e^u-1,e^v-1)\\ D^{\rm col}(u,v)&=D\big(\ln(1+u),\ln(1+v)\big)\\ S^{\rm col}(u,v)&=D^{\rm col}(S_1(u),S_2(v))\\ &=D\big(\ln(1+S_1(u)),\ln(1+S_2(v))\big)\\ \end{aligned} \]

难以写出 \(D(u,v),S^{\rm col}(u,v)\) 的封闭形式,但注意到只需要 \(\big[\frac{u^nv^m}{n!m!}\big]\) 系数,提取之

\[\begin{aligned} [\tfrac{u^nv^m}{n!m!}\big]S^{\rm col}(u,v) &=[\tfrac{u^nv^m}{n!m!}\big]\sum_{i=1}^{+\infty}\sum_{j=1}^{+\infty}c^{ij}\dfrac{\ln^i(1+S_1(u))\ln^j(1+S_2(v))}{i!j!}\\ &=\sum_{i=1}^{+\infty}\sum_{j=1}^{+\infty}c^{ij}[\tfrac{u^n}{n!}\big]\dfrac{\ln^i(1+S_1(u))}{i!}[\tfrac{v^m}{m!}\big]\dfrac{\ln^j(1+S_2(v))}{j!}\\ &=\sum_{i=1}^{+\infty}\sum_{j=1}^{+\infty}c^{ij}f_{n,i}g_{m,j} \end{aligned} \]

其中 \(f_{n,i}=[\tfrac{u^n}{n!}\big]\dfrac{\ln^i(1+S_1(u))}{i!},\ g_{m,j}=[\tfrac{v^m}{m!}\big]\dfrac{\ln^j(1+S_2(v))}{j!}\)。这是“幂的横截”,可以用拉格朗日反演计算,需要用到复合逆,可以 \(O(|W|n\log n)\) 牛迭求出。

然后利用 \(c^{ij}=c^{\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}}\),即可做到一次卷积

\[\begin{aligned} [\tfrac{u^nv^m}{n!m!}\big]S^{\rm col}(u,v) &=\sum_{i=1}^{+\infty}\sum_{j=1}^{+\infty}c^{\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}}f_{n,i}g_{m,j}\\ &=\sum_{k=2}^{+\infty}c^{\binom{k}{2}}\sum_{i=1}^kc^{-\binom{i}{2}}f_{n,i}c^{-\binom{k-i}{2}}g_{m,k-i}\\ \end{aligned} \]

后半部分和式可以卷积。

标签:big,sum,eps,反演,炫酷,mathcal,集合,rm,col
From: https://www.cnblogs.com/whisper6/p/17590699.html

相关文章

  • 这5个炫酷的python 数据可视化工具,你用过吗?
    常用的Python数据可视化小工具,推荐下面几个,熟练使用以后,做数据可视化不再是难题,并且,这几个数据可视化库在使用时可以取长补短,将数据信息表达发挥到极致,下面一起了解,都有哪些数据可视化库?可以帮助我们更好地呈现数据。1、Matplotlib:基础绘图库官网:https://www.matplotlib......
  • (五)DeepSpeed Chat: 一键式RLHF训练,让你的类ChatGPT千亿大模型提速省钱15倍
    DeepSpeedChat:一键式RLHF训练,让你的类ChatGPT千亿大模型提速省钱15倍如需引用DeepSpeedChat,请引用我们的arxivreport:@article{yao2023dschat,title={{DeepSpeed-Chat:Easy,FastandAffordableRLHFTrainingofChatGPT-likeModelsatAllScales}},autho......
  • [题解]AT_abc267_f [ABC267F] Exactly K Steps
    大家好,我是毒瘤,喜欢用玄学算法过题。发现题解区没有这个做法,于是来发一篇。思路不难发现如果一个点对\((u,v)\)的距离为\(d\),那么在这棵树以\(u\)为根时,\(v\)的深度为\(d\)。于是考虑换根DP。首先思考如何计算答案。显然我们可以将查询离线下来,然后当换根到以\(u\)......
  • 【论文翻译】DeepSeek-Coder-V2: Breaking the Barrier of Closed-Source Models in C
    本翻译来自大模型翻译,如有不对的地方,敬请谅解引言开源社区通过开发诸如StarCoder(Li等人,2023b;Lozhkov等人,2024)、CodeLlama(Roziere等人,2023)、DeepSeek-Coder(Guo等人,2024)和Codestral(MistralAI,2024)等开源代码模型,在推进代码智能方面取得了显著进展。这些模型的性能已稳步接近......
  • 莫比乌斯反演学习笔记
    \[\]前段时间学习了莫比乌斯反演,现在补一篇学习笔记吧。Step1:莫比乌斯函数首先我们来定义一下莫比乌斯函数\(\mu\),它的取值如下:\[\mu(n)=\left\{ \begin{array}{ll} 1\qquad\quadn=1\\ (-1)^k\quadn=p_1p_2\cdotsp_k\\ 0\qquad\quadotherwise \end{array}......
  • DeepSeek-Coder-V2: Breaking the Barrier of Closed-Source Models in Code Intellig
    DeepSeek-Coder-V2:BreakingtheBarrierofClosed-SourceModelsinCodeIntelligence相关链接:arxivgithub关键字:开源、代码智能、混合专家模型(MoE)、编程语言支持、上下文长度扩展摘要我们介绍了DeepSeek-Coder-V2,这是一个开源的混合专家(MoE)代码语言模型,其性......
  • 解释一下这段代码 npm i --no-save --legacy-peer-deps react@17
    这段命令是用于在Node.js项目中安装React17版本的一个指定操作,具体各部分含义如下:npmi或npminstall:这是用于在Node.js项目中安装包的命令,会根据package.json文件中的dependencies或devDependencies安装所有依赖,如果没有指定特定包,则会安装所有列出的依赖。--no-save:这......
  • DeepSORT(目标跟踪算法)中卡尔曼增益的理解
    DeepSORT(目标跟踪算法)中卡尔曼增益的理解flyfish先用最简单的例子来理解卡尔曼增益公式(1)首先,通过多次测量一个物理量,并使用取平均值的方式来计算其真实值:x......
  • 二项式反演小记
    篇幅有限,仅记录公式及极简证明。定义\[\begin{aligned}&f(n)=\sum_{i=0}^n(-1)^i{n\choosei}g(i)\Leftrightarrowg(n)=\sum_{i=0}^n(-1)^i{n\choosei}f(i)&(1)\\&f(n)=\sum_{i=0}^n{n\choosei}g(i)\Leftrightarrowg(n)=\sum_{i=0}^n(-1)^{n+i}{n\cho......
  • 【EI会议征稿通知】第四届能源工程与电力系统国际学术会议(EEPS 2024)
    第四届能源工程与电力系统国际学术会议(EEPS2024)20244th InternationalConferenceonEnergyEngineeringandPowerSystems   第四届能源工程与电力系统国际学术会议(EEPS2024),将于2024年8月9-11日在杭州召开,由杭州电子科技大学主办,杭州电子科技大学自动化学院承办......