Very concise C++ DP solution O(n) with explanation
Let\'s say f[i] denotes the number of days that is needed to visit room i for the first time, and g[i] denotes the number of days to visit room i for the second
Let\'s say f[i] denotes the number of days that is needed to visit room i for the first time, and g[i] denotes the number of days to visit room i for the second time. \nObviously we have f[0] = 1. Since 0 <= nextVisit[i] <= i, nextVisit[0] must be 0, so we also have g[0] = 2.\n\nNow let\'s do the calculation of f[i] and g[i] (1 <= i < n):\nConsidering that **0 <= nextVisit[i] <= i** (**with the nextVisit array we cannot proceed, only jump back**), the first time we reach room i, we must be coming from room i - 1 (even number of times). So we can say `f[i] = (g[i - 1] + 1) % MODN`\n\nTo calculate g[i], we must first reach room i taking f[i] days. Then we need to jump back to nextVisit[i]. Let\'s say we will need d days to restart from nextVisit[i] and get back to room i again. We will have: `g[i] = (f[i] + 1 + d)`\n\nThe question now comes to how do we calculate d: we can notice that before we jump back to room nextVisit[i], room nextVisit[i] must have been visited **even** number of times (remember we cannot proceed with odd number of room visits). **The same rule applies to when we restart from nextVisit[i] to get to room i for the first time (f[i])**. So we can have `d = f[i] - f[nextVisit[i]]`\n\nFinally we have `g[i] = (f[i] * 2 - f[nextVisit[i]] + 1) % MODN`\n```\nclass Solution {\n    const int MODN = 1000000007;\npublic:\n    int firstDayBeenInAllRooms(vector<int>& nextVisit) {\n        int n = nextVisit.size();\n        vector<long long> f(n, 0), g(n, 0);\n        f[0] = 1;\n        g[0] = 2;\n        for (int i = 1; i < n; ++i) {\n            f[i] = (g[i - 1] + 1) % MODN;\n            g[i] = (f[i] * 2 + MODN - f[nextVisit[i]] + 1) % MODN;\n        }\n        return (f[n - 1] + MODN - 1) % MODN;\n    }\n};\n```\nPlease let me know if you have any questions. Kindly upvote if this answer helped you! Thanks :-)
[]