题目链接
题目大意：
q∈[1,1e5],n∈[1,1000],mi∈[1,10]q\in[1,1e5],n\in[1,1000],m_i\in[1,10]q∈[1,1e5],n∈[1,1000],mi∈[1,10]
k,c∈[−1e9,1e9]k,c\in[-1e9,1e9]k,c∈[−1e9,1e9]
解题思路：
因为询问很多，那么我们不可能每次询问都暴力搜索而且k,ck,ck,c很大我们观察一下mim_imi才101010，我们是不是可以枚举从每个点的不同的状态出发，处理出所以的状态？我们发现对于mi∈[1,10]m_i\in[1,10]mi∈[1,10]，那么lca(1,...,9,10)=2520lca(1,...,9,10)=2520lca(1,...,9,10)=2520就是一个状态循环节就是从一个点出发累加上kik_iki，模上252025202520的y′y'y′和不模的yyy效果是一样的，因为252025202520是[1,10][1,10][1,10]里面的是倍数→y′≡y(modmi)\rightarrow y' \equiv y(mod\;m_i)→y′≡y(modmi)那么我们就可以设状态为(x,y)(x,y)(x,y)，就是到达了xxx这个点，现在的累加和%2520\%2520%2520为yyy的答案是多少那么我们不能暴力搜索，但是整个状态就n∗2520n*2520n∗2520那么我们可以记忆化搜索我们知道dfsdfsdfs是一条路径，实际上我们只是把一个点拆成了252025202520个，那么访问到了以前得状态得时候，那么是找到环了，那么我们可以去跟新答案了，就是找到这个环上有多少个不同得点？在回溯的时候记得更新访问过所以点的答案AC code
#include <bits/stdc++.h>#define mid ((l + r) >> 1)#define Lson rt << 1, l , mid#define Rson rt << 1|1, mid + 1, r#define ms(a,al) memset(a,al,sizeof(a))#define log2(a) log(a)/log(2)#define lowbit(x) ((-x) & x)#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)#define INF 0x3f3f3f3f#define LLF 0x3f3f3f3f3f3f3f3f#define f first#define s second#define endl '\n'using namespace std;const int N = 5e6 + 10, mod = 2520;const int maxn = 500010;const long double eps = 1e-5;const int EPS = 500 * 500;typedef long long ll;typedef unsigned long long ull;typedef pair<int,int> PII;typedef pair<ll,ll> PLL;typedef pair<double,double> PDD;template<typename T> void read(T &x) {x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;}template<typename T, typename... Args> void read(T &first, Args& ... args) {read(first);read(args...);}int n, cnt[N], js[N]; // cnt保存路径上的点，js是用来去重的，去除重复的点int ans[1010][mod+10];int depth[1010][mod+10];bool vis[1010][mod+10];vector<int> G[1010];int val[1010];inline int dfs(int u, int state) {vis[u][state] = 1;if(ans[u][state]) ans[u][state];int len = G[u].size();// system("pause");int nxtpoi = G[u][(state+val[u])%len];int nxtstate = (state+val[u]) % mod;if(vis[nxtpoi][nxtstate]) {// 如果下一个点是有答案的或者是访问过的if(ans[nxtpoi][nxtstate]) return ans[u][state] = ans[nxtpoi][nxtstate];// 这里记得赋值ans[u][state] 否则wa5int r = depth[u][state], l = depth[nxtpoi][nxtstate];for(int i = l; i <= r; ++ i) js[cnt[i]] = 0;for(int j = l; j <= r; ++ j) if(js[cnt[j]]==0) ans[u][state] ++, js[cnt[j]] = 1;return ans[u][state];}depth[nxtpoi][nxtstate] = depth[u][state]+1;cnt[depth[nxtpoi][nxtstate]] = nxtpoi;return ans[u][state] = dfs(nxtpoi,nxtstate);//每次return 都要跟新答案}int main() {// IOS;cin >> n;for(int i = 1; i <= n; ++ i) cin >> val[i], val[i] = (val[i] % mod + mod) % mod; // 先把所以的点都mod上2520for(int i = 1; i <= n; ++ i) {int num;cin >> num;for(int j = 1; j <= num; ++ j) {int x;cin >> x;G[i].push_back(x);}}int m;cin >> m;while(m--) {int x, y;cin >> x >> y;y = (y % mod + mod) % mod;cnt[0] = x;cout << dfs(x,y) << "\n";// 记忆化搜索}return 0;}
如果觉得《图论 ---- F. Graph Traveler 记忆化搜索 + 思维预处理（数论同余恒等式）》对你有帮助，请点赞、收藏，并留下你的观点哦！
