4
12
2015
1

论逗逼的自我修养之BC#37 D

论一道傻逼题是怎么出出来的...现在这题的[tex]O(m^6)[/tex]傻逼题解挂在BC首页上简直有一种身败名裂的感觉..

大致的题意就是求[tex]n[/tex]个点不少于[tex]m[/tex]条边的所有点度数都为偶数的无自环无重边带标号的无向图的个数。数据范围[tex]n\leq 10^{18}, m \leq 80[/tex]。

算法一:[tex]O(m^6)[/tex]

先不考虑边的限制,一个[tex]n[/tex]个点满足条件的图与[tex]n-1[/tex]个点的简单无向图一一对应。这个不难理解,一个[tex]n-1[/tex]个点的简单无向图我们可以加上第[tex]n[/tex]个点然后与所有度数为奇数的点连边,这样就可以得到一个[tex]n[/tex]个点的优美的图。

所以不考虑边数限制的话答案就是[tex]2^{\binom{n-1}{2}}[/tex]。接下来考虑去掉边数不到[tex]m[/tex]的优美的图的个数。因为[tex]n[/tex]比较大,所以比较难处理,考虑去掉孤立点的贡献,即求边数为[tex]m[/tex]点数为[tex]n[/tex]的每一个联通块都至少一条边的优美的图的个数,这样就可以在最后乘上组合数去掉贡献。考虑DP求解,令[tex]dp_{i,j,k}[/tex]表示[tex]i[/tex]个点,[tex]j[/tex]个奇点,[tex]k[/tex]条边的方案数,转移的时候考虑连向这些边的同时可能会有几个度数为0的点接上去。我们枚举新点连向多少个度数为0编号小于它的点,多少个度数为偶正数的点,多少个奇点,这是一个[tex]O(m^6)[/tex]的DP,然后打表一下就能过了。

这个是我最开始YY的标算..然而等到比赛开始..大爷们就想了各种各样的算法把我之前的标算给揍到了地底下..

算法二:[tex]O(m^5)[/tex]

可以发现[tex]n[/tex]个点边数不多于[tex]m[/tex]的优美的图的个数是关于[tex]n[/tex]的[tex]m[/tex]次多项式。这个还是很好理解的,因为在计算过程中,最多只有[tex]m[/tex]个点不是孤立点,而计算过程中唯一个[tex]n[/tex]有关的部分是从这[tex]n[/tex]个点中选出不是孤立点的点,其余的部分都是个[tex]n[/tex]无关的,产生最大次数的一项应该是[tex]\binom{n}{m}[/tex],所以是[tex]m[/tex]次的多项式。然后只需要DP出[tex]n[/tex]个点不超过[/tex]m[/tex]条边的前[tex]m[/tex]项然后插值得到系数就好了。暴力的DP是令[tex]dp_{i,j,k}[/tex]表示[tex]i[/tex]个点,[tex]j[/tex]个奇点,[tex]k[/tex]条边的方案数,转移的时候枚举连多少条边,有多少条连向奇点。

算法三:[tex]O(m^5)[/tex]

显然算法一里算孤立点是在秀逗。我们可以先不管孤立点,DP出[tex]n[/tex]个点[tex]m[/tex]条边的优美的图的个数,其中[tex]n[/tex]只要DP到[tex]m[/tex]就好了,然后考虑容斥出没有孤立点的情况,这是很简单的。令[tex]f_{i,j}[/tex]为没有孤立点的,[tex]g_{i,j}[/tex]为直接DP出来的数组,那么显然有:

[tex]f_{n,m}=g_{n,m}-\sum_{i=0}^{n-1}\binom{n}{i} \times f_{i,m}[/tex]

这样就可以得到算法一中要求的没有孤立点的优美的图的个数了。

以上两个算法的DP应该可以优化?所以应该可以得到一些复杂度低于[tex]O(m^5)[/tex]的做法。然而接下来这个算法终结了优化以上逗逼DP的过程..

算法四:[tex]O(m^2)[/tex]

(姿势学习自范爷某题)

令[tex]f_{i,j}[/tex]表示当前加入了[tex]i[/tex]条边,有[tex]j[/tex]个奇点的方案数,接下来考虑新插入一条边。讨论这一条边连接了的点的奇偶性,分三种情况:1.都是奇数,转移到[tex]f_{i+1,j-2}[/tex]。2.一个奇数一个偶数,转移到[tex]f_{i+1,j}[/tex]。3.都是偶数,转移到[tex]f_{i+1,j+1}[/tex]。

然而这样转移会产生重边,如果产生了重边,考虑同时删掉这两条边,此时所有点的奇偶性都不变,于是情况就规约到了[tex]f_{i-2,j}[/tex],显然新加入的边可以和先前加入的[tex]i-1[/tex]条边重复,所以要扣除的有重边的方案数就是[tex]f_{i-2,j} \times \binom{n}{2} \times (i-1)[/tex]。

所以就可以得到总的转移方程:

[tex]f_{i,j}=f_{i-1,j} \times j(n-j)+\binom{j+2}{2}f_{i-1,j+2}+\binom{n-j+2}{2}f_{i-1,j-2}[/tex]

         [tex]-\binom{n}{2}f_{i-2,j} \times (i-1)[/tex]

注意最后的答案要除以[tex]m![/tex](插入边的顺序对最后的图是没有影响的)。

所以说啊..这题的标算要比这题可以做到的最优算法要弱到不知道哪里去了..因为出题的时候本来是出C,所以也就没有怎么细想DP,随便YY了一个大暴力然后就走上了打表的不归路...

感觉这题实在是傻逼的我自己都说不出话来了..然而BC场上无人AC作为出题人我也是非常无奈的。

考前我还加强了D的pretest..然后A的pretest又放的这么强..

所以说啊..我其实打心底是很想成为一个业界良心送rating的出题人的..然而每一次出题都会因为一些莫名其妙的外部原因让大家产生我是业界毒瘤的错觉..这也不能怪我啊(无辜脸)

虽然我的外表是非洲人..但我有着一颗欧洲人的心..

Category: 论逗逼的自我修养系列 | Tags: | Read Count: 1858
Avatar_small
wxx 说:
2017年3月09日 13:28

算法四应该是手误吧...都是偶数:应该转移到f[i+1][j+2]?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com