首页 > 其他分享 >闲话 23.2.15

闲话 23.2.15

时间:2023-02-15 20:11:31浏览次数:62  
标签:连通 right 15 闲话 23.2 exp frac egf left

闲话

vscode 被我调 ntt 搞炸了 所以这篇博客直接在 cnblogs 上写了
寄(
update:不是 vscode,是除了浏览器外的部分

今日推歌:一人行者 - ilem feat. 心华
我知道你可能想说什么但是一人行者是真的很好听
所以今天我脑子里一直在循环播放 所以我推这首歌
而且感觉这歌能比较好的刻画一部分人群 反正我挺有感触的
所以听听?
虽然这首歌是 ilem 老师 16 年写的 但是确实很好听

连通图计数

有标号无向连通图计数

众所周知有标号无向图是由有标号无向连通图拼成的。假设有标号无向图的 egf 是 \(F\),则有标号无向连通图的 egf 就应当是 \(\ln F\),由于有标号 \(\text{Set}\) 构造的逆在 gf 上就是 \(\ln\)。\(F\) 的构造是简单的。

下面记有标号有根无向连通图的 egf 为 \(C\)。

边双连通图计数

假设有根无向边双连通图的 egf 是 \(B(x)\)。

考虑如何构造一个有根无向连通图。我们可以枚举一个极大边双联通分量的大小 \(k\),以及连在它上面的无向联通子图。前半部分的方案数是 \(B[k]\),后半部分的方案数的 egf 是 \(\exp(kC(x)) = \left(\exp C(x)\right)^k\)。这也就导出

\[C(x) = \sum_{k\ge 0} B[k] \left(\exp C(x)\right)^k \frac{x^k}{k!} = B(x\exp C(x)) \]

我们若设 \(F(x) = x\exp C(x)\),则有

\[B(x) = C\left(F^{\langle -1 \rangle}(x)\right) \]

这启发我们通过拉格朗日反演提取系数:

\[\begin{aligned} & [x^n]B(x) \\ = \ & [x^n]C\left(F^{\langle -1 \rangle}(x)\right) \\ = \ & \frac{1}{n}[x^{n - 1}] C'(x) \left(\frac{x}{x \exp C(x)}\right)^n \\ = \ & \frac{1}{n}[x^{n - 1}] C'(x) \exp\left (-n C(x)\right) \end{aligned}\]

这就有 \(O(n\log n)\) 提取单项的方式。记得除 \(n\)。

点双连通图计数

假设有根无向点双连通图的 egf 是 \(D(x)\)。

考虑如何构造一个有根无向连通图。由于根可能在多个点双连通分量内,考虑这些分量的交有且仅有根这一个节点,我们不妨求出删掉根后其中一个点双连通分量所在连通块的 egf,最后作 \(\text{Set}\) 构造再加入根即可。

下面只考虑 \(n > 1\) 的情况,这保证了每个点双连通分量的大小定大于等于 \(2\)。
我们可以枚举点双连通分量的大小 \(k + 1\)。删除根后点双联通分量的大小即为 \(k\)。如果删掉这个点双连通分量中所有边(而不是点),我们能得到 \(k\) 个连通块,它们的 egf 都是 \(C(x)\)。因此其中一个点双联通分量所在连通块的 egf 即为

\[\sum_{k \ge 0} D[k + 1] C^k(x) \frac{1}{k!} = D'(C(x)) \]

这也就导出

\[C(x) = x\exp D'(C(x)) \]

稍加变形得到

\[D'(C(x)) = \ln \frac{C(x)}{x} \]

我们若设 \(F(x) = \ln \dfrac{C(x)}{x}\),则有

\[D'(x) = F\left(C^{\langle -1 \rangle}(x)\right) \]

这启发我们通过拉格朗日反演提取系数:

\[\begin{aligned} & [x^n]D'(x) \\ = \ & [x^n]F\left(C^{\langle -1 \rangle}(x)\right) \\ = \ & \frac{1}{n}[x^{n - 1}] F'(x) \left(\frac{x}{C(x)}\right)^n \\ = \ & \frac{1}{n}[x^{n - 1}] F'(x) \left(\exp( -F(x))\right)^n \\ = \ & \frac{1}{n}[x^{n - 1}] F'(x) \exp( -nF(x)) \end{aligned}\]

这就有 \(O(n\log n)\) 提取单项的方式。

最终可以发现两个答案的形式是相似的。

标签:连通,right,15,闲话,23.2,exp,frac,egf,left
From: https://www.cnblogs.com/joke3579/p/chitchat230215.html

相关文章

  • ARC154E Reverse and Inversion(*)
    ARC154EReverseandInversionACrecord......
  • 2023.02.15 模拟赛小结
    2023.02.15模拟赛小结目录2023.02.15模拟赛小结更好的阅读体验戳此进入赛时思路T1T2T3T4UPD更好的阅读体验戳此进入啥正经人会在模拟赛用仨小时将普及难度的期望DP转......
  • LG-P6157 有趣的游戏 题解
    LG-P6157有趣的游戏Solution目录LG-P6157有趣的游戏Solution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定$n$个点的树,存在点权......
  • CF1534F2 Falling Sand (Hard Version)
    个人思路:每个点向相邻沙子连边,向本列和相邻\(2\)列下方第一个沙子连边。对于一个DAG,所有入度为\(0\)的点会覆盖全部点。我们缩点即可通过F1。但是这样做是过不了......
  • C语言学生课程选修管理系统[2023-02-15]
    C语言学生课程选修管理系统[2023-02-15]课程设计题目及要求本课题要求用C语言编写一个学生课程选修管理系统。学生课程选修系统用于学生选修学习课程。系统可以管理若干......
  • 算法杂记 2023/02/15
    算法杂记2023/02/15目录算法杂记2023/02/15453.MinimumMovestoEqualArrayElements462.MinimumMovestoEqualArrayElementsIInull今天分享的是两个力扣上的......
  • 15. CTFshow 萌新 web1
    一、代码<html><head><title>ctf.show萌新计划web1</title><metacharset="utf-8"></head><body><?php#包含数据库连接文件include("config.php");#判......
  • 与AI对话 -- 20230215 -- linux 启动参数与控制台
    linux启动参数console=ttyS0,115200n8console=tty0说明console=ttyS0,115200n8:指定系统使用ttyS0(ttyS1、ttyS2以此类推)串口作为主控台,115200n8意思是以115200即......
  • 2023.2.11-2.12
    zroi2524命题挺简单的,就是一开始以为顺序无关考虑高维前缀和去了。用\(\text{Trie}\)树的做法比较显然,总状态数是\(2^n\log2^n\)的。zroi2526题目手玩一下发现......
  • ERROR: [HLS 200-1715] Encountered problem during source synthesis
    工具:Vitis_HLS2022.2我尝试用HLS部署一个神经网络时,在HLSSynthesis阶段出现如下信息,且无其他任何报错ERROR:[HLS200-1715]Encounteredproblemduringsourcesynt......