小島みなこの競プロ日常
460 subscribers
5.18K photos
288 videos
283 files
6.95K links
Download Telegram
这个题还真的挺难的。。。。推清楚的话代码量倒是约等于 0 .。。
考虑用 GF 处理这个计数问题。。。
第一步是考虑怎么破环为链。。。但是这里细节有点多。。我们先考虑链的情况吧
首先可以对 m 进行倍增。。
想到这一步就成功一大半了。。
之后我们发现实际上是要计数一个 01 序列。。然后不能出现两个连续的 1.。
这个东西一共有五种情况。。。
核心思想是对这个序列中每次出现两个连续的 0 ,就拆成两个物品,然后去做完全背包。
搞出 path 之后 cycle 就变得简单了。。。所以核心难点是上面这个 5 种情况。。很容易讨论漏掉。。
我觉得这个题非常 nice。。。
wait ,这玩意不是可以 O(n) 么