首页 > 其他分享 >SS241106C. 此时此刻的光辉

SS241106C. 此时此刻的光辉

时间:2024-11-07 16:10:33浏览次数:4  
标签:此时此刻 右边 限制 个点 SS241106C 状态 光辉 FWT

SS241106C. 此时此刻的光辉

题意

给你 \(n\) 个点,每个点需要被染成 \(0/1/2\) 三种颜色之一,有 \(m\) 种限制,每个限制形如【\(u\) 不是颜色 \(x\) or \(v\) 不是颜色 \(y\)】,问你满足限制的涂色方案数。

思路

拜谢 dxw。

题解提到了 FWT 是什么东西,好吓人啊。

这里是题解的做法一,不知道 FWT 是什么东西,也不知道和 FWT 有什么关系。

感觉这个做法偏暴力。

考虑 meet in the middle 方法。

左边 \(B\) 个点,右边 \(n-B\) 个点,枚举左边和右边的涂色状态,是 \(O(3^{B}+3^{n-B})\) 的。

计算对于左边每个状态,右边有多少个状态是合法的。

可以处理处左边状态会对右边造成什么限制,限制形如【能不能涂 \(0/1/2\)】,因为不可能三种颜色都不能涂,因此限制的种类有 \(7\) 种。

考虑预处理出右边每种限制的情况下有多少种状态是符合这种限制的。

限制情况一共 \(7^{n-B}\) 种。

然后做完了,时间复杂度 \(O(3^{B}+21^{n-B})\)?实际上可以对每个状态枚举合法的限制,每个状态的合法限制只有 \(4^{n-B}\) 种。因此时间复杂度 \(O((3^B+12^{n-B})\times poly(n))\)。

\(n-B\) 取 \(6\) 或者 \(7\) 都是可以的。

标签:此时此刻,右边,限制,个点,SS241106C,状态,光辉,FWT
From: https://www.cnblogs.com/liyixin0514/p/18531095

相关文章

  • 诺贝尔物理学奖的新篇章:机器学习与神经网络的光辉时刻
    文章目录前言一、从理论到实践:机器学习的物理基础二、跨学科融合:开启智能时代的新纪元三、技术创新:推动科学研究的革命四、社会影响:促进公平与可持续发展五、伦理与挑战:确保技术的健康发展六、未来展望:开启智能时代的无限可能结语前言在科学界的璀璨星河中,诺贝尔奖......
  • 不能选择此时此刻之前的时间
    <el-date-pickertype="datetime"v-model="transshipmentTime"placeholder="请选择"style="width:100%;"value-format="yyyy-MM-ddHH:mm:ss":picker-options="pickerOptions"//在这里配置@change="ha......
  • 活在此时此刻
    这些是截图。观心法,但是部分也是迂腐......
  • 此时此刻,非你莫属!SoloPi 贡献者活动正式开启
    SoloPi贡献者活动正式开始了,欢迎大家踊跃报名,提供各种形式的贡献,我们为其中出众的贡献者准备了相当丰厚的奖品,并提供与测试大咖进行一对一交流的机会。关于SoloPiSoloPi是......
  • [Ynoi2015] 此时此刻的光辉
    题传做完CF1422F再做这道题就肥肠有感觉了。如果你不想再看一题那么我就无耻推销一下我的题解。\[\text{————————我是分割线————————}\]请确保你......