题解：P15013 FUN!!

· · 题解

为什么我题解区一篇题解都看不懂……

本题解按照思考方向一步一步推导。

::::info[对题目给出的条件的一些思考]

:::info[图的每个点都只有一条出边说明什么?]

说明构造的图构成了一个内向基环树森林。

:::

:::info[每个点往后跳 n+k 步意味着什么?]

最终每个点都会跳到它所在的基环树的环上的点。

:::

:::info[此时，如果把 i 连向它要到达的点 a_i，基环树会发生什么变化？]

你会惊奇的发现基环树的环不会发生改变，但是不属于环上的点都会挂在它最终应该到的点上。

所以我们把 i 连向 a_i，看它形成的每棵基环树是否是一个环，然后每个环上的点挂了若干个点的形态。

如果形态是这样的，那么挂在环上的点可以构造完环上节点后再来构造它们，这时可以很简单的构造出来，这样就可以不用管这些点，所以把这些排除，现在只考虑环上的点。

:::

::::

::::info[拼好环]

我们一开始连出来的环（之后叫原环）就是它们保持关系的最小单位，我们不可能去把这些环拆掉，否则就会有些关系满足不了了。

但是如果我们不对原环进行任何操作，那么可能存在构造不出来的情况。

这里就要用到一个神秘的东西来说明了。

:::info[一个长度为 l 的环上，如果一个点每次向后走 s 步，直到回到这个点，问会走到多少个点？]

结论就是最终的经过的点是 \frac{l}{\gcd(l,s)}。

我不太会证明，你可以手玩几组（毕竟我就是这么玩出来的），然后在网上搜索一下（好像是和同余的最小解有关）。

:::

所以一个环你不去动它，它有可能跳出来的点本质上是几个长度相等的环。

我们可以利用这个性质，把若干长度相同的环拼在一起，就有可能跳成功。

设 s=n+k。

:::info[例子]

比如有 3 个长度为 6 的原环，当 n+k=15 时，它们独自是构造不出来的。

但是，把它们拼起来：

就可以满足条件。

:::

:::info[考虑拼出来的环长度为 L，那么它会划分成什么？]

利用上面的结论，会包含 g=\gcd(L,s) 个长度为 \frac{L}{g} 个小环（即由这些原环拼成）。

:::

:::info[反过来，原环长度为 l，拼出来的环环长的可能值？]

设有 g 个原环，那么拼出来的新环长度为 L=gl，此时要满足 \gcd(L,s)=g，即 \gcd(gl,s)=g，我们惊奇的发现 gcd(l,\frac{s}{g})=1！

:::

:::info[如何暴力拼环的过程]

其实是完全背包。

对于长度为 l 的环，假设有 c_l 个，找出所有合法的 g。那么每次可以选出 g 个原环拼在一起。注意拼成的新环其实我们不需用在去拼了，因为那还不如一次性就把它拼好。

最后看它能不能做到刚好用掉 c_l 个。

:::

:::info[对于一个 g，gcd(l,\frac{s}{g})=1 本质上是要满足什么？]

把 l,s 表示为素数的乘积形式，那么 gcd(l,\frac{s}{g})=1 本质上是把 s 中出现的 l 的质因子全部踢掉，然后再把 s 中其他的质因子踢掉几个，但是你会发现这样还不如只选 l 中的质因子更优，因为其他的 g 都是它的倍数，所以我们只需要判断 c_l 能不能被它整除即可。时间复杂度 O(n\log n)。

:::

::::

::::success[Code]

#include<bits/stdc++.h>
#define YES puts("Yes")
#define NO puts("No")
using namespace std;
const int N=5e5+5;
int t,n,k,a[N];
int head[N],tot;
int state[N],from[N];
bool cycle[N];
int c[N];
struct edge{
    int to,next;
};
edge e[N<<1];
int isnotp[N];
vector<int>d[N];
void add(int from,int to){
    e[++tot]={to,head[from]};
    head[from]=tot;
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') f=(ch=='-'?-f:f),ch=getchar();
    while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
} 
bool dfs(int u){
    state[u]=1;
    bool find=false;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(state[v]==0){
            from[v]=u;
            if(dfs(v)) find=true;
        }
        else if(state[v]==1){
            int len=1;
            cycle[v]=1;
            for(int i=u;i!=v;i=from[i]) cycle[i]=1,len++;
            c[len]++;
            find=true;
        }
        if(find) break;
    }
    state[u]=2;
    return find;
}
bool check(int l,int s){
    if(!c[l]) return true;
    int ans=1;
    for(int v:d[l]){
        while(s%v==0) ans*=v,s/=v;
    }
    return c[l]%ans==0;
}
void clear(){
    for(int i=1;i<=n;i++){
        state[i]=from[i]=0;
        cycle[i]=0;
        head[i]=0;
        c[i]=0;
    }
    tot=0;
}
void solve(){
    n=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) add(i,a[i]);
    for(int i=1;i<=n;i++){
        if(!state[i]) dfs(i);
    }
    for(int i=1;i<=n;i++){
        if(!cycle[a[i]]){
            NO,clear();
            return;
        }
    }
    int s=n+k;
    for(int i=1;i<=n;i++){
        if(!check(i,s)){
            NO,clear();
            return;
        }
    }
    YES,clear();
}
int main(){
    t=read();
    isnotp[1]=1;
    for(int i=2;i<N;i++){
        if(!isnotp[i]){
            d[i].push_back(i);
            for(int j=i*2;j<N;j+=i){
                isnotp[j]=1;
                d[j].push_back(i);
            }
        }
    }
    while(t--) solve();
    cerr<<'\n'<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
    return 0;
}

::::