【HDU】6038 - Function（置换群）

#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define PI acos(-1.0)
const LL MOD = 1000000007;
int a[100000+100],b[100000+100];
bool vis[100000+100];
bool visB[100000+100];
LL num[100000+100];     //循环阶数 
int main()
{
//  freopen("input.txt","r",stdin);
//    freopen("output2.txt","w",stdout);
    int n,m;
    int Case = 1;
    while (~scanf ("%d %d",&n,&m))
    {
        for (int i = 0 ; i < n ; i++)
        {
            scanf ("%d",&a[i]);
            vis[i] = false;
        }
        for (int i = 0 ; i < m ; i++)
        {
            scanf ("%d",&b[i]);
//          num[i+1] = 0;       //这么初始化就WA 
            visB[i] = false;
        }
        CLR(num,0);     //这么初始化才能AC，如果a的群很大，而b的群很小的时候，会搜到循环阶数大于m的群 
        for (int i = 0 ; i < m ; i++)
        {
            if (!visB[i])
            {
                visB[i] = true;
                int ant = 1;
                int t = b[i];
                while (t != i)
                {
                    visB[t] = true;
                    t = b[t];
                    ant++;
                }
                num[ant] = (num[ant] + ant) % MOD;
            }
        }
        LL ans = 1;
        for (int i = 0 ; i < n ; i++)
        {
            if (!vis[i])
            {
                vis[i] = true;
                int ant = 1;
                int t = a[i];
                while (t != i)
                {
                    ant++;
                    vis[t] = true;
                    t = a[t];
                }
                LL cnt = 0;     //循环阶数是b的循环阶数的倍数的个数
                for (int j = 1 ; j*j <= ant ; j++)
                {
                    if (ant % j == 0)
                    {
                        if (j*j != ant)
                            cnt += (num[ant/j] + num[j]) % MOD;
                        else
                            cnt = (cnt + num[j]) % MOD;
                    }
                }
                ans = ans*cnt % MOD;
            }
        }
        printf ("Case #%d: %lld\n",Case++,ans);
    }
    return 0;
}