CF1863G Swaps 题解

题目链接

点击打开链接

题目解法

这么牛的题！！！

先套路地建图，连边 \(i\to a_i\)
考虑交换 \(a_i\) 和 \(a_{a_i}\) 的含义，我们把边 \(i\to a_i,\;a_i\to a_{a_i}\) 变成了 \(i\to a_{a_i}\) 和 \(a_i\) 的自环

每次交换的话分析过于复杂，考虑打 \(tag\)，我们把所有操作过的 \(i\)，在 \(i\to a_i\) 的边上打 \(tag\)
打完 \(tag\) 之后的图，点 \(i\) 会指到哪个点？
如果点 \(i\) 有入边被打上 \(tag\)，那么 \(i\) 就是自环；否则一直往后跳边，指到第一条未被打 \(tag\) 的边指向的点就是 \(i\) 会指到的点

从上面的结论不难发现，每个点至多只会有一个入边被打 \(tag\)，因为如果一个点有入边被打过 \(tag\) 了，那么这个点就是自环，再打这个点其他入边的 \(tag\) 不会对序列产生影响

看似答案就是 \(\prod\limits_{i=1}^n(in_i+1)\)，\(in_i\) 为点 \(i\) 的入度
但是环的情况很特殊
我们可以手画一下单一简单环的情况，发现有 \(n-1\) 的点的入边打上 \(tag\) 之后，整个简单环已经被拆分成 \(n-1\) 的简单环了，也就是说 \(n\) 个点的简单环，至多只能有 \(n-1\) 个点的入边打上 \(tag\)
推广至非简单环的情况，可以手玩一下一个简单环 + 一条入边的情况，发现如果只染非环边和环上的 \(n-2\) 条边，环上的 \(n\) 个点是不会拆分成 \(n\) 个单独的自环的
也就是说，只有染的 \(n-1\) 条边都在环上，才会使环上的每个点都是自环

不难得到答案为 \(\prod\limits_{circle_i}(\prod\limits_{x\in circle_i}(in_x+1)-\sum\limits_{x\in circle}in_x)\prod\limits_{x\notin circle} (in_x+1)\)
时间复杂度 \(O(n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=1000010,P=1e9+7;
int n,ans=1,a[N],in[N];
int col[N],cntcol;
int pas[N],cnt,rv[N];
bool cir[N];
vector<int> G[N];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
void dfs(int u){
    col[u]=cntcol,pas[++cnt]=u,rv[u]=cnt;
    for(int v:G[u]){
        if(col[v]==cntcol){
            int val1=1,val2=0;
            F(i,rv[v],cnt) cir[pas[i]]=1,val1=1ll*val1*(in[pas[i]]+1)%P,inc(val2,in[pas[i]]);
            ans=1ll*ans*(val1-val2+P)%P;
        }
        if(!col[v]) dfs(v);
    }
}
int main(){
    read(n);
    F(i,1,n) read(a[i]);
    F(i,1,n) G[i].pb(a[i]),in[a[i]]++;
    F(i,1,n) if(!col[i]) cntcol++,dfs(i);
    F(i,1,n) if(!cir[i]) ans=1ll*ans*(in[i]+1)%P;
    printf("%d\n",ans);
    return 0;
}