LC 1997. 访问完所有房间的第一天

https://leetcode-cn.com/contest/weekly-contest-257/problems/first-day-where-you-have-been-in-all-the-rooms/

初看这题目觉得似乎有什么公式可以推导出来，但是后来觉得这个公式太复杂以至于没有办法推导出来，因为往回跳的位置其实是不确定的。

这题有好几个关键点：

  1. 如果某个房间是奇数次访问，那么之前的房间肯定都是偶数次访问过。
  2. 如果某个房间p是奇数次访问，那么
    • 我们需要立刻调回到 next[p] 上
    • 然后继续回调若干次，重新回到next[p]上
    • 然后前进到next[p]+1上, 此时next[p]+1肯定是奇数
    • 接着就和处理next[p]一样
  3. 所以这里的关键是，如果我们回调到某个位置x（那么此时x一定是奇数次访问），那么重新回到x需要多久，这个可以通过动态规划得到，假设是 `cyc[x]`
  4. 那么如果访问房间p是奇数次，那么
    • 我们回调到 x=next[p] 上，然后重新回到 next[p]，就有 cyc[x]+1次跳跃
    • 前进到x+1, 然后重新回到 x+1, 就有 cyc[x+1]+1次跳跃
    • 直到p-1节点上，最后还有一次跳跃
    • 这个过程可以通过前缀和来求解

理清楚了过程代码写起来就比较简单，而且好像也没有什么边界情况。 

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        n = len(nextVisit)
        acc = [0] * (n + 1)
        cyc = [0] * n

        MOD = 10 ** 9 + 7

        for i in range(n):
            back = nextVisit[i]
            if back == i:
                cyc[i] = 1
            else:
                cyc[i] = (acc[i] - acc[back]) + (i - back + 1)
                cyc[i] %= MOD
            acc[i + 1] = acc[i] + cyc[i]
            acc[i + 1] %= MOD

        # print(cyc)

        ans = 0
        for i in range(n - 1):
            # how many steps from i to i+1
            ans += cyc[i] + 1
            ans %= MOD

        return ans