做游戏CG分享的网站,粤icp备网站建设 中企动力广州,有文化底蕴的公众号名字,wordpress微信登录开发文档题目
给定一个长度为n(n1e6)的序列#xff0c;第i个数ai(1ain)#xff0c;
操作#xff1a;你可以将当前i位置的数和a[i]位置的数交换
交换可以操作任意次#xff0c;求所有本质不同的数组的数量#xff0c;答案对1e97取模
思路来源
力扣群 潼神 心得
感…题目
给定一个长度为n(n1e6)的序列第i个数ai(1ain)
操作你可以将当前i位置的数和a[i]位置的数交换
交换可以操作任意次求所有本质不同的数组的数量答案对1e97取模
思路来源
力扣群 潼神 心得
感觉已经说的很详尽了甚至没什么需要补充的地方...
不难发现自环的情况和2的环的情况是统一的所以dfs找环即可 组合题更多的是一种无从下手的感觉需要多培养手玩性质的能力
比如发现a-b-c到a-c,b-b这个性质然后再着手计数
代码
#includebits/stdc.h
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef unsigned ui;
//typedef __uint128_t L;
typedef unsigned long long L;
typedef unsigned long long ull;
const int N1e610,mod1e97;
int n,v,to[N],deg[N];
vectorinte[N];
int stk[N],c,ans1;
bool vis[N],in[N];
void dfs(int u){if(!u)return;stk[c]u;in[u]1;vis[u]1;int vto[u];if(in[v]){//环的情况 统一了自环的情况int res1,sub0;while(c){int wstk[c--];in[w]0;res1ll*res*(deg[w]1)%mod;sub(subdeg[w])%mod;if(wv)break;}res(resmod-sub)%mod;ans1ll*ans*res%mod;}if(!vis[v])dfs(v);
}
int main(){sci(n);rep(i,1,n){sci(v);to[i]v;deg[v];}rep(i,1,n){if(!vis[i]){dfs(i);}while(c){int wstk[c--];in[w]0;ans1ll*ans*(deg[w]1)%mod;}}printf(%d\n,ans);return 0;
}
