Function这道题我当时一直很迷，到底怎么来的啊，为什么会这样啊？？
然后看了题解才知道，原来是找循环啊。
已知f(i)=b[f(a(i)]，则
f(0) = b[f(a[0])] = b[f(2)]
f[1] = b[f(a[1])] = b[f(0)]
f[2] = b[f(a[2])] = b[f(1)]
其实这道题可以转化为求环的问题，有多少种方式可以构成题目要求的环，即b的环可以有多少种方式画成a的环。
第一个样例我们可以知道 a0->a1->a0, a2->a2, b0->b0, b1->b1。
则和a同构的环有b0->b0->b0, b1->b1->b1, b0->b0, b1->b1四个
第二个样例我们可以知道a0->a2->a1->a0 b0->b0 b1->b2->b3->b1
则和a同构的环有b1->b2->b3->b1 b2->b3->b1->b2 b3->b1->b2->b3 b0->b0->b0->b0四个
然后找出所有环的长度，是a环的因子的就加起来，最后将所有的乘起来（为什么是乘起来？？因为组合数学啊(●‘?‘●)）
ll ans=1; for (int i=0; i<va.size(); i++) { ll num=0; for (int j=0; j<vb.size(); j++) { if (va[i]%vb[j]==0) num+=vb[j]; } ans = ans*num%mod; }
代码：
/* gyt Live up to every day */ #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<cstring> #include<queue> #include<set> #include<string> #include<map> #include <time.h> #define PI acos(-1) using namespace std; typedef long long ll; typedef double db; const int maxn = 1e5+10; const ll maxm = 1e7; const ll mod = 1e9+7; const int INF = 1<<30; const db eps = 1e-8; int a[maxn], b[maxn]; bool visa[maxn], visb[maxn]; vector<ll>va, vb; int ca=1; int flag; void init() { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(visa, 0, sizeof(visa)); memset(visb, 0, sizeof(visb)); va.clear(); vb.clear(); } void solve() { int n, m; while(scanf("%d%d", &n, &m)!=EOF) { init(); for (int i=0; i<n; i++) { scanf("%d", &a[i]); } for (int i=0; i<m; i++) { scanf("%d", &b[i]); } for (int i=0; i<n; i++) { if (visa[i]) continue; int x=i; int sum=0; while(x!=a[x]) { if (visa[x]) break; visa[x]=1; sum++; // cout<<x<<" "<<a[x]<<endl; x=a[x]; } //cout<<x<<endl; if (x==i) { // cout<<"sum:"<<sum<<endl; if (sum==0) va.push_back(1); else va.push_back(sum); } else { x=i; int num=0; while(x!=a[x]) { if (num>=sum) break; visa[x]=0; num++; x=a[x]; } visa[i]=1; va.push_back(1); } } for (int i=0; i<m; i++) { if (visb[i]) continue; int x=i; int sum=0; while(x!=b[x]) { if (visb[x]) break; visb[x]=1; sum++; x=b[x]; } if (x==i) { if (sum==0) vb.push_back(1); else vb.push_back(sum); } else { x=i; int num=0; while(x!=a[x]) { if (num>=sum) break; visb[x]=0; num++; x=b[x]; } visb[i]=1; vb.push_back(1); } } ll ans=1; for (int i=0; i<va.size(); i++) { ll num=0; for (int j=0; j<vb.size(); j++) { if (va[i]%vb[j]==0) num+=vb[j]; } ans = ans*num%mod; } printf("Case #%d: %lld\n", ca++, ans); } } int main() { //freopen("in.txt","r",stdin); // freopen("kingdom.in","r",stdin); //freopen("kingdom.out","w",stdout); int t=1; // scanf("%d", &t); while(t--) solve(); }
原文：http://www.cnblogs.com/gggyt/p/7241328.html