10.2闲话

发布时间 2023-10-02 21:28:18作者: crimson000

今天就返校力???

但是上午还没返校,看 B 站看爽了。然后抽时间打了把妖妖梦 E 难度,3 残通关,诱导机体真好混关???

下午返校,高铁上手机玩爽了。

jimmy 让报牛客的模拟赛,借此从我爸那怒赚 200 块(。

具体过程:我跟我爸说要报这玩意,我爸微信转我 200,然后我用我爸支付宝付的钱???。血赚!

晚上看昨天正睿的视频,发现题有点逆天的属于是,感觉自己水平太拉了???,菜逼???

突然有个问题:luogu 上的囧仙和 B 站上的囧是一个人吗/yiw,有人知道可以回答下吗。

明天上午模拟赛晚上模拟赛,摆了。

感觉最近也没时间做 agc 了啊,好事。

lrx 学长问为啥人均摘星(,其实我是好早之前摘的了,当时入坑了也差不多两年才摘的,完全不像 wyy(我同桌)这个底力超人入坑一年摘星???

假期和 wyy 卷音游把翡翠鸡卷到 1far 了,爽,谱也挺爽的,但是听说他癖了(


推歌:Ego Eimi -BlackY feat. Risa Yuzuki

十月新番 《Arcaea 之痴女好可怕》 OP


放个之前写过的题解吧。

P6596

\(F[i, j]\)\(i\) 个点,\(j\) 条割边的无向连通图的数量。我们考虑去掉 \(1\) 号点所在的双连通分量,那么整张图就会分为一堆连通块。我们再设 \(G[i, j, k]\)\(i\) 个点,\(j\) 条割边,\(k\) 个连通块的无向图的数量。那么我们枚举 \(1\) 号点所在连通分量的大小,就能对于 \(0<j<i\) 得到转移方程:

\[F[i, j]=\sum \limits _{p=1}^{i-1}(F[p, 0]\times\dbinom{i-1}{p-1}\times \sum \limits _{q=1}^j (G[i-p,j-q,q]\times p^q)) \]

\(p\) 枚举的是 \(1\) 号点所在连通分量的大小,\(q\) 枚举的是 \(1\) 号点所在的连通分量去掉后会剩下多少连通块,而割边也会随之减少 \(q\),可以看下图理解:

然后 \(p^q\) 的含义即为我们每个连通分量一定会选择 \(1\) 号点所在的连通块中一个点连边,那么方案数即为 \(p^q\)

再考虑求出 \(F[i, 0]\)。根据容斥,我们只需要用连通图的数量减去含割边的图的数量 \(c\) 即可。因此:

\[F[i, 0]=c_i-\sum \limits _{j=1}^{i-1}F[i,j] \]

最后我们再考虑求出 \(G\) 数组。我们依旧枚举 \(1\) 号点所在连通块大小 \(p\),同时我们再枚举一号点连通块割边的数量 \(q\),我们就能得到转移方程:

\[G[i,j,k]=\sum\limits_{p=1}^i\sum\limits _{q=0}^j(f[p,q]\times p\times \dbinom{i-1}{p-1}\times G[i-p,j-q,k-1]) \]

我们注意到其中多乘了一个 \(p\),这其实代表着我们求出的是“有根双连通分量”,因为我们要在这个双连通分量中选一个点来和一开始去掉的边双连边。因此我们多乘了一个 \(p\),而在别的情景中需要视情况而定。

时间复杂度:\(O(n^5)\)

问就是和 01Trie 学的(