HDU 7050. Link with Limit

发表于 分类于

链接

https://acm.hdu.edu.cn/showproblem.php?pid=7050

题意

Link has a function $f(x)$, where $x$ and $f(x)$ are both integers in $[1,n]$.

Let $f_n(x)=f(f_{n−1}(x))$ and $f_1(x)=f(x)$, he define the power of a number $x$ as:

$$g(x)=\lim_{n\rightarrow+\infty}\frac{1}{n}\sum_{i=1}^nf_i(x)$$

He wants to know whether $x$ has the same power for all $x\in[1,n]$.

思路

将 $i$ 与 $f_i$ 之间连一条有向边，易发现从任意一点出发最终一定会来到一个环。

那么我们只要判断环的平均值是否相等即可。

每个点只会有一条出边，只可能在一个环里，拓扑排序求出哪些点在环里，反拓扑序求出每个点所在环权值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const int N=1e5+5;
int f[N],in[N];
bool st[N];
VI a,b;
void topo(int n) {
    queue<int> q;
    a.clear();
    for(int i=1;i<=n;i++) if(!in[i]) q.push(i);
    while(SZ(q)) {
        int u=q.front();
        a.PB(u);
        q.pop();
        if(--in[f[u]]==0) q.push(f[u]);
    }
}
LL sum=0;
void dfs(int u) {
    st[u]=true;
    sum+=f[u];
    b.PB(u);
    if(!st[f[u]]) dfs(f[u]);
}
void solve(int n) {
    topo(n);
    vector<pair<LL,int>> w(n+1);
    for(int i=1;i<=n;i++) st[i]=false;
    for(int i=1;i<=n;i++) if(in[i]&&!st[i]) {
        sum=0;
        b.clear();
        dfs(i);
        for(auto x:b) w[x]=MP(sum,SZ(b));
    }
    for(int i=SZ(a)-1;~i;i--) w[a[i]]=w[f[a[i]]];
    for(int i=2;i<=n;i++) if(w[1].FI*w[i].SE!=w[i].FI*w[1].SE) {
        cout<<"NO"<<'\n';
        return;
    }
    cout<<"YES"<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--) {
        int n;cin>>n;
        for(int i=1;i<=n;i++) in[i]=0;
        for(int i=1;i<=n;i++) cin>>f[i],++in[f[i]];
        solve(n);
    }
    return 0;
}