题目链接：https://codeforces.com/contest/1787/problem/D
大致题意：给你一个n长度的数组a，你将从1位置开始，每次都会跳到 i+ai 的位置，如果该位置在1-n之间，
那么继续跳；如果不在，那么结束；
现在，你可以令x位置上的数变成y，即ax = y；
问你，有多少种改法，使得更改后，你从1开始，能够结束跳；
解题思路：
我们思考，不能够结束的条件是什么？
很容易可以知道，当我们从1开始跳的时候，后面会进入一个环里面，那么我们就不能结束；
于是，我们可以分情况讨论一下，在一开始的情况下，从1开始是否会进入一个环；
1：如果不会进入一个环：
那么就是一个链，从1开始，一直到不在1-n之间结尾的链；
我们考虑：
如果x不在链内，那么不管y是什么，1最终都会按链的循序跳出去；
如果x在链内，那么只有当y是x之前包括x的位置的时候，链会产生环，于是1就不能从链跳出去；
2：如果会进入一个环：
我们考虑：
如果x不在环内，那么不管y是什么，1最终都会在环内；
如果x在环内，那么只有 当x+y的位置是不在1-n之间， 或者 x+y位置上的可以跳出1-n；
于是，考虑到现在，此题就可以结束了，接下来就是实现，详细可以看一下代码；
时间复杂度：O（n）；
ac代码：
#include<bits/stdc++.h>
int main()
{
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int T; std::cin >> T;
while (T--)
{
int n; std::cin >> n;
std::vector<int> vis(n + 1, 0), D(n + 1, 0), nums(n + 1, 0);
std::vector<std::vector<int>> G(n + 1);
for (int i = 1; i <= n; ++i)
{
std::cin >> nums[i];
int p = (nums[i] + i<1 || nums[i] + i>n) ? 0 : nums[i] + i;
G[p].push_back(i);
}
std::function<int(int)> DFS = [&](int u)
{
D[u] = 1;
for (auto v : G[u])D[u] += DFS(v);
return D[u];
}; DFS(0);
//D【0】表示可以跳出1-n的个数
//D【i】表示通过 i位置 能够跳出 1-n 的个数
if (D[1])//1在链
{
long long ans = 1ll * n * (2 * n + 1);
for (int u = 1; u >= 1 && u <= n; u += nums[u])ans -= (n + 1 - D[0] + D[u]);
std::cout << ans << "\n"; continue;
}
//1在环内
long long ans = 0;
for (int u = 1; !vis[u]; u += nums[u])ans++, vis[u] = 1;
ans *= (D[0] + n);
std::cout << ans << "\n";
}
return 0;
}
这题主要难点在于思维以及判环实现，有思维但是实现不出来也是一种悲剧（乐
标签：TypeDB,std,Rated,nums,int,位置,那么,Div From： https://www.cnblogs.com/ACMER-XiCen/p/17101334.html