tco12round2A hard evenpaths

论语文的重要性……
我是看bzoj的中文题面的。
然后看到这句:“迷宫有一个性质,对于每个房间,一旦通过走廊离开房间,则无法再回到这个房间。”
以为是说我们从0到1的路径只能是简单路径,然后这个图可以是非DAG。
结果在这个错误的理解下,yy了半天都yy不出来啥靠谱的做法。
后来ydc跟我说这个好像是说这个图是dag, 卧槽立马就可做起来了
先不说会不会做……看错题肯定就跪了,这状态绝壁省选滚粗= =

第一次看到不太裸的fwt。
显然那个不确定状态的房间数目小于等于32是让你折半搜索中途相遇法之类的东西搞。
那么就中途相遇搞吧。
弄半天之后就能得到一个模型……

已知a[1<<17],b[1<<17]两个数组的每个元素的数值。
然后求c[1<<17]每个元素的数值。
c[i]的计算公式为
for i in range(0,1<<17):
    for j in range(0,1<<17):
        c[i&j]+=a[i]*b[j]

套用之前srm518的hard的做法就好。
传送门:我写的srm518nim的题解
如果嫌我讲的不清楚可以看picks的讲解:
传送门:http://picks.logdown.com/posts/192421-the-solution-to-topcoder-open-2012s-hard-problems

Comments

comments powered by Disqus