题解：P15013 FUN!! / [SNOW] - 13

· · 题解

:::info[什么样的人生是失败的？（第四弹）] 点击标题可以看见上一次坠机。

发力了，写了 3.5h 的 B，严肃没开 C 痛失部分分。

被绿题击碎了呜呜呜。

最难绷的是前面写的几个假做法能过样例，结果把假做法叉掉以后和正解差不多的代码一直过不了样例。

虚空调试 1h 后发现一直在拿步幅的式子算圈数，真没绷住。

结果改对以后又花了半个小时在卡常 /fn :::

300pts 遗憾离场。

为什么会变成这样子呢？我问我自己。

直接按照题意建图可以出来一个基环树森林。这张图我们称为原图。

保底跑 n 次，然后显然每一棵基环树树高都不会超过 n，于是最后肯定会在环上跑。

考虑重建后的图，上面的结论也就意味着原图有儿子的点一定得在环上。

显然指向一个「环上的点」的「环上的点」有且仅有一个。

那也就是说合法的局面除了环上的点都不会被指向。

不管怎么样先跑拓扑找环。基环树找环的实现可以参考 P8655 发现环。

把环上的点标记出来，按照上面的那个结论先筛一轮。

因为是森林，所以最后会得到许多互相独立的环。

注意到一个长度为 s 的环，以走 k 步判定相邻的话，事实上会被拆成 \gcd(s,k) 个长度相同的环。

于是可以考虑把若干个环拼在一起使得被拆出来是合法的。

根据这个结论，显然只能拼大小相同的环。

于是我们知道，若 g 个长度为 s 的环拼起来以后是合法的，当且仅当满足 \gcd(g\times s,k)=g。

注意到这个式子其实不等价于 \gcd(s,k)=1，因为即使不满足这个式子 g 也可以把 s 对结果的贡献换出去。

不过从这个角度思考，一个合格的 g 必然需要把所有 s 的贡献给换出去。

假设 g_{min} 是最小的合法 g，那么也就是说对于任意一个合法的 g 都有 g_{min}|g。

注意到能够合法的把这些环全部解决掉的重要条件是能够通过一定的拼接方式把环的数量消耗掉，既然有上面的性质，那么拼大环一定可以用拼小环来解决，所以只需要求 g_{min} 就好。

其实这里只需要模拟换出去的过程就做完了，暴力实现即可。

时间复杂度 O(n\log^2 V)，其中值域 V\le 10^9。

应该有更加优秀的实现方式，不管了现在能过就行。

如果你最后一个 Subtask 取得了整整 4 个 TLE，大概率不是这里的问题，也许是前面被卡常了。

我也不知道 O(n) 的拓扑找环为什么会那么慢，卡不过去的话可以尝试使用下列科技（并非科技）取得好一点的常数：

啊但是事实上改链式前向星可以快 400ms /lengh

#include<bits/stdc++.h>
#define int unsigned int
using namespace std;
int gcd(int a,int b){
    int flc=min(__builtin_ctz(a),__builtin_ctz(b)),tmp;
    a>>=__builtin_ctz(a);
    b>>=__builtin_ctz(b);
    if(a<b)swap(a,b);
    while(a!=b){
        a-=b;
        a>>=__builtin_ctz(a);
        if(a>b)continue;
        tmp=a;
        a=b;
        b=tmp;
    }
    return (a<<flc);
}
int read(){
    int sum=0,fish=1;
    char c=getchar_unlocked();
    while((c<'0'||c>'9')&&c!='-')c=getchar_unlocked();
    if(c=='-')fish=-1,c=getchar_unlocked();
    while(c>='0'&&c<='9')sum=sum*10+(c-'0'),c=getchar_unlocked();
    return sum*fish;
}
void print(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x<10)putchar_unlocked(x+'0');
    else print(x/10),putchar_unlocked(x%10+'0');
}
struct fish{
    int nex,t;
}a[1000005];
int head[500005],tp;
void add(int u,int v){
    a[++tp].nex=head[u];
    a[tp].t=v;
    head[u]=tp;
}
int f[500005];
bool vis[500005];
int fa[500005];
int find(int x){
    return(x==fa[x]?x:fa[x]=find(fa[x]));
}
bool is[500005];
int ans[500005];
int qaq[500005];
int pap[500005];
void solve(){
    int n=read();
    int pwp=read();
    pwp+=n;tp=0;
    for(int i=1;i<=n;i++)
    head[i]=pap[i]=is[i]=ans[i]=f[i]=vis[i]=0,fa[i]=i;
    for(int i=1;i<=n;i++){
        int u=read(),v=i;
        qaq[i]=u;
        add(u,v),add(v,u);
        f[u]++,f[v]++;
        fa[find(i)]=find(u);
    }
    queue<int>q;
    for(int i=1;i<=n;i++)
    if(f[i]==1)q.push(i),vis[i]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=a[i].nex){
            if(vis[a[i].t])continue;
            f[a[i].t]--;
            if(f[a[i].t]==1)
            q.push(a[i].t),
            vis[a[i].t]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        for(int j=head[i];j;j=a[j].nex){
            if(!vis[a[j].t])
            is[a[j].t]=1;
        }
    }
    for(int i=1;i<=n;i++){
        ans[find(i)]+=is[i];
        if(!is[qaq[i]]){
            puts("No");
            return;
        }
    }
    for(int i=1;i<=n;i++)
    if(ans[i]>1&&gcd(pwp,ans[i])!=1){
        pap[ans[i]]++;
    }
    for(int i=1;i<=n;i++)
    if(pap[i]){
        int x=gcd(pwp,i);
        while(gcd(x*i,pwp)!=x)x=gcd(x*i,pwp);
        if(pap[i]%x){
            puts("No");
            return;
        }
    }
    puts("Yes");
}
signed main(){
    int t=read();
    while(t--)solve();
    return 0;
}
// 魔女把几枚银币投进钱箱里，这么说：
//「稍微跟我聊聊吧？」

// 灰色的发丝摇曳，她露出了柔和的微笑。