Concise C++ with Explanation | DP + Prefix Sum | O(n)
Note 1: To the pass any index i the number of visits must become even \nIf the number of visits are odd you will end up going a index j = nextVisit[i] with 0 <=
**Note 1:** To the pass any index `i` the number of visits must become even \nIf the number of visits are odd you will end up going a index `j = nextVisit[i]` with `0 <= j <= i` (Since `0 <= nextVisit[i] <= i`)\n\nAssume `days[i]` = number of days required to pass `i` if you visit index `i` for the fist time\n\n**Note 2** If you visited `i` for the first time, it would always be an odd visit, and you will have to go to `nextVisit[i]`.\n\nNow let `j = nextVisit[i]`\n\n**Case 1**\nIf `j == i` then you will again reach `i` and number of visits will become even and you can move to `i+1`. Thus, `days[i] = 2`\n\n**Case 2**\nIf `j < i`, then this visit to `j` will always be odd one (*Because you have already passed `j` earlier and thus number of visits must have become even*).\nThus, to calculate `days[i]` = number of days required to pass `i`, you need to first pass `j`, then you will reach `j+1`, and now you have to pass `j+1`, then you reach `j+2` and so on. And then you will finally arrive at `i` and this time number of visits will be even and thus you can go to `i+1`.\nThus = `days[i] = 2 + days[j] + days[j+1] + days[j+2] + ... + days[i-1]`\n`2` becaue you also arrive at i 2 times.\nBut note that doing this naively will cause TLE thus you can use prefix sum approach to optimize the solution.\n\n```\nint mod = 1000000007;\n\nclass Solution {\npublic:\n    int firstDayBeenInAllRooms(vector<int>& nextVisit) {\n        int n = nextVisit.size();\n        vector<int> days(n);\n\t\t// days[i] = number of days required to pass i if you visit index i for the fist time\n        vector<int> pre(n+1);\n        pre[0] = 0;\n        // pre[i] = days[0] + days[1] + ... + days[i-1]\n        for (int i=0; i<n; i++) {\n            int j = nextVisit[i];\n            if (j == i) {\n                days[i] = 2;\n            } else {\n                assert(j < i);\n                // days[i] = 2 + (days[j] + days[j+1] + days[j+2] + ... + days[i-1]);\n                days[i] = 2 + (pre[i] - pre[j]);\n                days[i] = days[i] % mod;\n                if (days[i] < 0) days[i] += mod;\n            }\n            pre[i+1] = (pre[i] + days[i]) % mod;\n        }\n        return (pre[n-1]) % mod;\n    }\n};\n```
[]