HDU 6038 Function（思维+寻找循环节）

http://acm.hdu.edu.cn/showproblem.php?pid=6038

题意：
给出两个序列，一个是0~n-1的排列a，另一个是0~m-1的排列b，现在求满足的f的个数。

思路：

先看一下样例吧：

对于这组数来说，假如我们先指定了f（0）对应的在b中的值，那么根据第2个式子，就可以得出f（1），根据f（1）就又可以得出f（2），最后根据f（2）就可以检验f（0）的值是否正确。

这也就是说，对于a中的一个循环节，只要确定了其中一个数所映射的值，那么其它数就都被相应的确定了。

所以我们需要先计算出a和b中的循环节个数和每个循环节对应的个数，然后根据循环节的因子关系就可以判断是否成立。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn = 1e5 + ;

 const int mod = 1e9+;

 int n, m;

 int a[maxn], b[maxn];

 int vis[maxn];

 vector<int> A;

 vector<int> B;

 int main()

 {

     //freopen("in.txt","r",stdin);

     int kase=;

     while(~scanf("%d%d",&n,&m))

     {

         for(int i=;i<n;i++)  scanf("%d",&a[i]);

         for(int i=;i<m;i++)  scanf("%d",&b[i]);

         A.clear();

         memset(vis,,sizeof(vis));

         for(int i=;i<n;i++)

         {

             int cur=i,cnt=;

             if(!vis[i])

             {

                 vis[i]=;

                 while(a[cur]!=i)

                 {

                     cur=a[cur];

                     vis[cur]=;

                     cnt++;

                 }

                 A.push_back(cnt);

             }

         }

         B.clear();

         memset(vis,,sizeof(vis));

         for(int i=;i<m;i++)

         {

             int cur=i, cnt=;

             if(!vis[i])

             {

                 vis[i]=;

                 while(b[cur]!=i)

                 {

                     cur=b[cur];

                     vis[cur]=;

                     cnt++;

                 }

                 B.push_back(cnt);

             }

         }

         ll ans=;

         for(int i=;i<A.size();i++)

         {

             ll tmp=;

             for(int j=;j<B.size();j++)

             {

                 if(A[i]%B[j]==)  tmp=(tmp+B[j])%mod;

             }

             ans=ans*tmp%mod;

         }

         printf("Case #%d: %d\n",++kase,ans);

     }

     return ;

 }