当前位置: 代码迷 >> 综合 >> 【CodeForces】【搜索】【思维】1218H Function Composition
  详细解决方案

【CodeForces】【搜索】【思维】1218H Function Composition

热度:95   发布时间:2023-11-21 06:41:02.0

CodeForces 1218H Function Composition

题目大意

给定一个长度为NNN的序列A(1≤Ai≤N)A(1\le A_i\le N)A(1Ai?N),现在定义一个函数如下:

  • f(i,1)=Aif(i,1)=A_if(i,1)=Ai?
  • f(i,m)=Af(i,m?1)f(i,m)=A_{f(i,m-1)}f(i,m)=Af(i,m?1)?

给定m,ym,ym,y,求有多少个xxx使得f(x,m)=yf(x,m)=yf(x,m)=y,多组询问。

分析

考虑将这个问题转化为一个图论问题:当Ax=yA_x=yAx?=y时,我们连一条从xxxyyy的有向边。

对于这个图,我们仔细观察一下可以发现如下性质:

  • 每个节点的出度都是111
  • 每个连通块都可以被单独考虑计算贡献;
  • 查询可以变成找出节点yyymmm级祖先有多少个;
  • 每个连通块中只有一个环。

考虑离线处理询问。

我们先预处理出所有的环。然后枚举每个位置上的询问,分两种情况讨论:

  • yyy不属于任何一个环:我们需要统计的就是距离当前深度等于mmm的点的数量,这个可以用 DFS 来完成:先删掉环上的所有边,然后在记录每个深度上的节点数量,就可以求出距离yyy的为mmm的点。
  • yyy在环上,我们将从环上的任意一个节点zzz开始遍历。设zzzyyy的距离为ttt,环长为lll。我们先删掉zzz的出边(它只有这么一条),那么我们就可以比较轻松回答询问了,这样我们只需要计算距离yyy节点为(m+t)modl(m+t)\mod l(m+t)modl的节点数量了。

这东西说着容易,写起来贼难受。。。

参考代码

#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;typedef long long ll;
const int Maxn = 2e5;struct DSU {
    int fa[Maxn + 5];void init(int n) {
    for(int i = 1; i <= n; i++)fa[i] = i;}int find(int u) {
    return u == fa[u] ? u : fa[u] = find(fa[u]);}bool unite(int u, int v) {
    u = find(u), v = find(v);if(u == v) return false;fa[u] = v;return true;}
};struct Query {
    int id, typ;ll m;Query(){
    }Query(int _typ, int _id, ll _m) {
    typ = _typ, id = _id, m = _m;}bool operator < (const Query &rhs) const {
    return m == rhs.m ? typ > rhs.typ : m > rhs.m;}
};struct Edge {
    int to;Edge *nxt;
};int N, A[Maxn + 5];
DSU s;Edge pool[Maxn * 2 + 5];
Edge *G[Maxn + 5], *ecnt = &pool[0];
inline void addedge(int u, int v) {
    Edge *p = ++ecnt;p->to = v, p->nxt = G[u];G[u] = p;
}vector<int> circles[Maxn + 5];
int cnt_circle;bool on_circle[Maxn + 5];
bool DFS(int u, int tp) {
    if(u == tp) {
    on_circle[u] = true;circles[cnt_circle].push_back(u);return true;}for(Edge *p = G[u]; p != NULL; p = p->nxt) {
    int v = p->to;if(!DFS(v, tp)) continue;on_circle[u] = true, circles[cnt_circle].push_back(u);return true;}return false;
}vector<Query> Q[Maxn + 5];int len, cnt[Maxn + 5];
priority_queue<Query> q;
int mxdep;
int ans[Maxn + 5], res[Maxn + 5];
inline int nxt(int x) {
    return x == len - 1 ? 0 : x + 1;}
void DFS(int u, int dep, int cirid, int pos) {
    q.push(Query(-1, circles[cirid][pos], dep));mxdep = max(mxdep, dep);if(!on_circle[u])for(int i = 0; i < (int)Q[u].size(); i++)if(dep + Q[u][i].m <= Maxn)ans[Q[u][i].id] -= cnt[dep + Q[u][i].m];cnt[dep]++;for(Edge *p = G[u]; p != NULL; p = p->nxt) {
    int v = p->to;if(on_circle[v]) continue;DFS(v, dep + 1, cirid, nxt(pos));}if(!on_circle[u])for(int i = 0; i < (int)Q[u].size(); i++)if(dep + Q[u][i].m <= Maxn)ans[Q[u][i].id] += cnt[dep + Q[u][i].m];
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d", &N);s.init(N);for(int i = 1; i <= N; i++) {
    scanf("%d", &A[i]);if(!s.unite(A[i], i)) {
    cnt_circle++, DFS(i, A[i]);reverse(circles[cnt_circle].begin(), circles[cnt_circle].end());}addedge(A[i], i);}int _;scanf("%d", &_);for(int i = 1; i <= _; i++) {
    ll m;int y;scanf("%lld %d", &m, &y);Q[y].push_back(Query(0, i, m));}for(int i = 1; i <= cnt_circle; i++) {
    len = (int)circles[i].size();for(int j = 0; j < len; j++) {
    int u = circles[i][j];mxdep = 0;DFS(u, 0, i, j);for(int k = 0; k <= mxdep; k++) cnt[k] = 0;for(int k = 0; k < (int)Q[u].size(); k++) {
    int v = circles[i][(j + Q[u][k].m) % len];q.push(Query(Q[u][k].id, v, Q[u][k].m));}}while(!q.empty()) {
    Query tmp = q.top();q.pop();if(tmp.typ == -1) res[tmp.id]++;else ans[tmp.typ] = res[tmp.id];}}for(int i = 1; i <= _; i++)printf("%d\n", ans[i]);return 0;
}
  相关解决方案