[洛谷P4841]城市规划

我真的菜,这道题从冬令营day0开始想起想到现在才想出来,然后发现真的是一道多项式求逆板子题。我已经菜出一种境界了。
下面分享一下我做这道题的经历(欢迎大家来嘲讽我):
首先看到这道题我就想了一个神奇的$O(n^3)$的DP,貌似和$n!$暴力一样只能拿20分,感觉特别不爽。这个做法是这样的:
考虑我们做Dinic的时候一开始对一个图分的层(可能是我网络流做多了脑子做傻了),然后可以发现一张任意的无向简单连通图都可以以1为源点唯一地表示为一个分层的模式。所以我们DP一下这个分层的模式就可以了。我们发现转移下一层的代价只与上一层的个数有关,所以我们定义状态:$f(i,j)$表示i个节点,分层之后最后一层有j个的简单无向联通图的个数。然后这个一个$2d/1d$动态规划,我不知道怎么优化。我一直觉得这个想法很精妙,所以一直陷在这个深坑里跳不出来。这非常好地说明了我是傻逼。
我感觉正解状态应该是一维的,但是我之前的想法怎么也优化不到一维。最终我恼羞成怒,强行把它搞到一维。那状态是什么呢?肯定是$f(i)$表示i个点的无向简单联通图的个数了。那么我考虑转移,考虑第i个点是不是割点,如果是割点,那么枚举割掉i之后1所在联通块大小,然后随便转移一下就可以了,但是不是割点怎么办啊?我怎么知道啊。
所以我又鸽了,我好菜了。我突然发现貌似可以把所有简单无向图的个数算出来,然后减去不联通的个数。怎么减呢?枚举1所在联通块有多少个点就可以了。于是我非常开心地写出了一个$1d/1d$动态规划:
$f(i)=2^{C_i^2}-\displaystyle\sum_{j=1}^{i-1}C_{i-1}^{j-1}f(j)2^{C_{i-j}^2}$
那么我们把它拆开来:
$f(i)=2^{C_i^2}-(i-1)!\displaystyle\sum_{j=1}^{i-1}\frac{f(j)}{(j-1)!}\times\frac{2^{C_{i-j}^2}}{(i-j)!}$
感觉这个$(i-1)!$特别烦,那么我们把它除掉:
$\frac{f(i)}{(i-1)!}=\frac{2^{C_i^2}}{(i-1)!}-\displaystyle\sum_{j=1}^{i-1}\frac{f(j)}{(j-1)!}\times\frac{2^{C_{i-j}^2}}{(i-j)!}$
设$A(x)=\frac{f(x)}{(x-1)!}$,$B(x)=\frac{2^{C_x^2}}{(x-1)!}$,$C(x)=\frac{2^{C_x^2}}{x!}$
那么原式子相当于:
$A(x)=B(x)-A(x)C(x)$
变形一下:
$A(x)=\frac{B(x)}{C(x)+1}$
B和C我们都是知道的,那么按照这个式子算一下A,然后用A就可以求出$f(n)$了。
代码:

Tagged with:

发表评论