题目
你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。
最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。在接下来的几天中，你访问房间的 次序 将根据下面的 规则 决定：
- 假设某一天，你访问
i号房间。 - 如果算上本次访问，访问
i号房间的次数为 奇数 ，那么 第二天 需要访问nextVisit[i]所指定的房间，其中0 <= nextVisit[i] <= i。 - 如果算上本次访问，访问
i号房间的次数为 偶数 ，那么 第二天 需要访问(i + 1) mod n号房间。
请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 109 + 7 取余后的结果。
示例 1：
输入：nextVisit = [0,0]
输出2
解释：
- 第 0 天，你访问房间 0 。访问 0 号房间的总次数为 1 ，次数为奇数。
下一天你需要访问房间的编号是 nextVisit[0] = 0 - 第 1 天，你访问房间 0 。访问 0 号房间的总次数为 2 ，次数为偶数。
下一天你需要访问房间的编号是 (0 + 1) mod 2 = 1 - 第 2 天，你访问房间 1 。这是你第一次完成访问所有房间的那天。
示例 2：
输入：nextVisit = [0,0,2]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,0,0,1,2,…] 。
第 6 天是你访问完所有房间的第一天。
示例 3：
输入：nextVisit = [0,1,2,0]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,1,2,2,3,…] 。
第 6 天是你访问完所有房间的第一天。
提示：
n == nextVisit.length2 <= n <= 1050 <= nextVisit[i] <= i
我的题解
题解（动归）
这个奇偶数访问的设定实际就是让访问一个房间后需要再往前访问，再回到当前位置才能继续向下。这个过程就像一个循环，或者说一个口袋。口袋的口就是当前访问的这个位置，而口袋里是所有在这个循环区间内的小循环。口袋需要计算口袋的口（访问了两次）和口袋内所有的循环，因为要全部重新走一遍才能回到当前位置。
在这个过程中，显然需要用到多次重复的累加，可以使用前缀和加速这个过程，否则会TLE。
代码如下
class Solution {
public:
int firstDayBeenInAllRooms(vector<int>& nextVisit) {
int n = nextVisit.size();
if(n==1){
return 0;
}
vector<int> visit_loop_count = vector<int>(n);
// 初始为2
visit_loop_count[0] = 2;
// 下面使用了前缀和，不太容易理解
for(int i=1;i<n;i++){
int sum;
if(nextVisit[i]>=1)
{
sum = visit_loop_count[i-1]-visit_loop_count[nextVisit[i]-1];
sum = sum<0?sum+(int)(1e9+7):sum;
}
else
sum = visit_loop_count[i-1];
visit_loop_count[i] = (visit_loop_count[i-1]+sum+2)%(int)(1e9 + 7);
}
return visit_loop_count[n-2];
//容易理解的没有加前缀和的代码如下：
// vector<int> visit_loop_count = vector<int>(nextVisit.size(), 0);
// for(int i=0;i<nextVisit.size();i++){
// int sum = 0;
// for(int j=nextVisit[i];j<i;j++){
// sum = (sum+visit_loop_count[j])%(int)(1e9 + 7);
// }
// visit_loop_count[i] = sum+2;
// }
// int ret = 0;
// for(int i=0;i<nextVisit.size()-1;i++){
// ret = (ret+visit_loop_count[i])%(int)(1e9 + 7);
// }
// return ret;
}
};class Solution {
public:
int firstDayBeenInAllRooms(vector<int>& nextVisit) {
int n = nextVisit.size();
if(n==1){
return 0;
}
vector<int> visit_loop_count = vector<int>(n);
// 初始为2
visit_loop_count[0] = 2;
// 下面使用了前缀和，不太容易理解
for(int i=1;i<n;i++){
int sum;
if(nextVisit[i]>=1)
{
sum = visit_loop_count[i-1]-visit_loop_count[nextVisit[i]-1];
sum = sum<0?sum+(int)(1e9+7):sum;
}
else
sum = visit_loop_count[i-1];
visit_loop_count[i] = (visit_loop_count[i-1]+sum+2)%(int)(1e9 + 7);
}
return visit_loop_count[n-2];
//容易理解的没有加前缀和的代码如下：
// vector<int> visit_loop_count = vector<int>(nextVisit.size(), 0);
// for(int i=0;i<nextVisit.size();i++){
// int sum = 0;
// for(int j=nextVisit[i];j<i;j++){
// sum = (sum+visit_loop_count[j])%(int)(1e9 + 7);
// }
// visit_loop_count[i] = sum+2;
// }
// int ret = 0;
// for(int i=0;i<nextVisit.size()-1;i++){
// ret = (ret+visit_loop_count[i])%(int)(1e9 + 7);
// }
// return ret;
}
};官方题解
值得注意的是，官方题解中有更好的取余处理方法（注意其中的+mod)：
for (int i = 1; i < len; i++) {
int to = nextVisit[i];
dp[i] = 2 + dp[i - 1];
if (to != 0) {
dp[i] = (dp[i] - dp[to - 1] + mod) % mod; //避免负数
}
dp[i] = (dp[i] + dp[i - 1]) % mod;
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/first-day-where-you-have-been-in-all-the-rooms/solutions/2710218/fang-wen-wan-suo-you-fang-jian-de-di-yi-p7fc2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。取余模板
另外，也有人使用了取余操作模板
static constexpr int mod = 1000000007;
class modint {
public:
int val;
inline modint(int val_ = 0) : val(val_) {}
inline modint &operator=(int val_) { return val = val_, *this; }
inline modint &operator+=(const modint &k) { return val = val + k.val >= mod ? val + k.val - mod : val + k.val, *this; }
inline modint &operator-=(const modint &k) { return val = val - k.val < 0 ? val - k.val + mod : val - k.val, *this; }
inline modint &operator*=(const modint &k) { return val = 1ll * val * k.val % mod, *this; }
inline modint &operator^=(int k) {
modint res = 1, tmp = *this;
for (; k; k >>= 1, tmp *= tmp)
if (k & 1)
res *= tmp;
return val = res.val, *this;
}
inline modint &operator/=(modint k) { return *this *= (k ^= mod - 2); }
inline modint &operator+=(int k) { return val = val + k >= mod ? (val + k) % mod : val + k, *this; }
inline modint &operator-=(int k) { return val = val < k ? val - k + mod : val - k, *this; }
inline modint &operator*=(int k) { return val = 1ll * val * k % mod, *this; }
inline modint &operator/=(int k) { return *this *= ((modint(k)) ^= mod - 2); }
template <class T>
friend modint operator+(modint a, T b) { return a += b; }
template <class T>
friend modint operator-(modint a, T b) { return a -= b; }
template <class T>
friend modint operator*(modint a, T b) { return a *= b; }
template <class T>
friend modint operator^(modint a, T b) { return a /= b; }
template <class T>
friend modint operator/(modint a, T b) { return a /= b; }
friend modint operator^(modint a, int b) { return a ^= b; }
friend bool operator==(modint a, int b) { return a.val == b; }
friend bool operator!=(modint a, int b) { return a.val != b; }
inline bool operator!() { return !val; }
inline modint operator-() { return val ? mod - val : 0; }
inline modint &operator++() { return *this += 1; }
inline modint &operator--() { return *this -= 1; }
friend ostream &operator<<(ostream &os, const modint &n) { return os << n.val; }
};
class Solution {
public:
int firstDayBeenInAllRooms(vector<int>& nextVisit) {
int n = nextVisit.size();
vector<modint> dp(n, 0);
dp[1] = 2;
for (int i = 2; i < n; ++i) {
dp[i] = (dp[i - 1] - dp[nextVisit[i - 1]] + dp[i - 1] + 2);
}
return dp[n - 1].val;
}
};完成时间
2024-03-28：[ 用时: 38 m 37 s ]
题目链接
https://leetcode.cn/problems/first-day-where-you-have-been-in-all-the-rooms/
