[C++] O(n) Explanation
Let\'s say we enter room#i for the first time.\nTwo cases:\n if nextVisit[i] == i : going to need 2 additional days to get past this room\n else (if nextVisit[i
Let\'s say we enter room#`i` for the first time.\nTwo cases:\n* if `nextVisit[i] == i` : going to need 2 additional days to get past this room\n* else (if `nextVisit[i] < i`): we get sent back to room#`nextVisit[i]`. And we have to do the sequence again where we go from room#`nextVisit[i]` to room#`i`\n\nTo do this in linear time, we just have to store/cache the total days (from the beginning) it took us to getPastRoom `i`, and a variable to keep track of how many days have past since the beginning.\n\n```\nclass Solution {\npublic:\n    int firstDayBeenInAllRooms(vector<int>& nextVisit) {\n        int n = nextVisit.size();\n        vector<long long> daysToGetPast(n, 0);\n        long long day = 0;\n        int MOD = 1e9+7;\n        \n        for (int i = 0; i < n-1; ++i) {\n            if (nextVisit[i] == i) {\n                day = (day+2)%MOD;\n            }\n            else {\n                \n\t\t\t\tlong long p = 0; // p:= time to go from beginning to enter room#nextVisit[i]\n                if (nextVisit[i] > 0) p = daysToGetPast[nextVisit[i]-1];\n\t\t\t\t\n\t\t\t\t// additional time to go from room#nextVisit[i]->entering room#[i]\n                day = (((2*(day%MOD))%MOD-(p%MOD))+MOD)%MOD;\n\t\t\t\t// we visit room#i twice, so need to add that to total time\n                day = (day+2)%MOD;\n            }\n\t\t\t// cache the number of days required to get past room[i-1]\n            daysToGetPast[i] = day%MOD;\n        }\n\t\t\n\t\t// time to visit all rooms = time required to enter last (n-1) room = time required to get past second-last (n-2th) room\n        return (int) daysToGetPast[n-2];\n    }\n};\n```
[]