题解：AT_abc389_g [ABC389G] Odd Even Graph

· · 题解

场上大脑被标号分配卡死了。没有困难的性质需要观察，只要找到自然的方法，顺着计数就能做出来。

看到要关注每个点的最短路，那么肯定是要先将图分层，就像这样。

换言之我们计数若干层点的“组合体”的数目（组合体和图形成双射）。这些组合体要求：

设计状态 f_{i,n1,m,d,0/1} 表示有 i 个点 m 条边的组合体数目，奇偶点之差为 d，最后一层有 n1 个点，最后一层是奇数层呢还是偶数层呢。

转移枚举新一层点数 s 和边数 x。这里 x 既包括两层之间的边，也包括下一层自己内部随意连的边。

下意识地设 h_{n1,s,x} 表示转移系数，这样转移就是

f_{i,n1,m,d,op}\times h_{n1,s,x}\times{i-1+s\choose s}\to f_{\ldots}

组合数是为了分配标号，减一是因为 1 一定在第一层。接下来想想，为了让这个方程是对的，h 的两个点集应是已经标号的。

那么求 h 的方法就很清晰了，对于每个 s 的点枚举它向 n1 连了 a(a\gt 1) 条边那就是 n1\choose a 种方案，乘起来。

比如我要算两层之间连了 x' 条边，这个数量就是

\sum_{a_1+a_2+\ldots+a_s=x'}\prod{n1\choose a_i}

还没算新层内部的连边呢。我可以先做上面这部分，接着同层转移就可以求出最终的 h 了。

内部连边就是在 s\choose 2 条边里选啊，这个不必多说了。

我们进行一个代码的写，在 n=30 计算次数达到了 2\times 10^9 左右。

因此进行一个枝的剪（或者直接开 O2），具体可以看我的代码。atcoder 上在不开 O2 情况下运行了三百多毫秒。

然而本地 n=30 跑了两秒。

AC 链接