F. Function
time limit per test1 second
memory limit per test128 megabytes
inputstandard input
outputstandard output
You are given a permutation a obtained from 0 to (n−1), and a permutation b obtained from 0 to (m−1).

Let's define a function f, which maps each integer between 0 and (n−1), to an integer between 0 and (m−1).

Please calculate the number of different functions f satisfying that f(i)=bf(ai) for each i.

Two functions are considered different if and only if there exists at least one integer mapped to different integers in these functions.

The answer can be a bit large, so you should output it modulo (109+7) instead.

Input
The input contains multiple test cases.

For each test case, the first line contains two integers n, m (1≤n,m≤105).

The second line contains n integers, the i-th number of which is ai−1 (0≤ai−1≤n−1).

The third line contains m integers, the i-th number of which is bi−1 (0≤bi−1≤m−1).

It is guaranteed that the sum of n and the sum of m in all test cases are no more than 106 respectively.

Output
For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to the corresponding case.

Example
inputCopy
3 2
1 0 2
0 1
3 4
2 0 1
0 2 3 1
outputCopy
Case #1: 4
Case #2: 4

题目描述：

给出排列a:0~n-1,排列b:0~m-1。问存在多少个双射f,满足对每个i都有f[i]=b_f[a[i]]。

有一个写得很清楚的题解：

 

 加一些我自己的理解：

 

也就是在这一循环中,b的周期是l_b,a的周期是l_a。（显然l_a>=l_b）由群论的知识l_b应该是l_a的因数。

这样计算a每个循环节长度的对应能使用b的循环节的方案数，再用乘法原理如上解决。

代码：

#include<bits/stdc++.h>
#define sd(x) scanf("%d",&x)
#define lsd(x) scanf("%lld",&x)
#define sf(x) scanf("%lf",&x)
#define ms(x,y) memset(x,y,sizeof x)
#define fu(i,a,b) for(register int i=a;i<=b;i++)
#define fd(i,a,b) for(register int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define range(a,x,y) a+x,a+y+x
#define dbug printf("bbbk\n")
#define R register
using namespace std;
//using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> P;
const int N=1e5+99;
const int MN=1e7+9;
const ll mod=1e9+7;
const int MAX=1e9;
const ll INF=1e9+7;
int a[N],b[N];//循环节的长度
map<int,int> lpa,lpb;//存储a和b的循环节长度对应个数
bool vis[N];
int loop(int *a,int s)//从s出发，计算s在a数组的循环节长度
{
    int sz=0;
    while(!vis[s])
    {
        vis[s]=1;
        s=a[s];sz++;
    }
    return sz;
}
void work(int *a,int &n,map<int,int> &lp)
{
    for(int i=0;i<n;i++)
    {
        if(vis[i]) continue;
        lp[loop(a,i)]++;
    }
}
ll qpow(ll x,ll n)
{
    ll res=1;
    while(n)
    {
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
void init()
{
    lpa.clear();lpb.clear();
}
int main()
{
    //freopen("t.txt","r",stdin);
    int cas=0,n,m;
    while(cin>>n>>m)
    {
        fu(i,0,n-1) cin>>a[i];
        fu(i,0,m-1) cin>>b[i];
        init();
        ll ans=1;
        ms(vis,0);
        work(a,n,lpa);
        ms(vis,0);
        work(b,m,lpb);
        for(auto x:lpa)//x:长度和个数
        {
            int len=x.first,times=x.second;
            ll tmp=0;
            for(int i=1;i<=sqrt(len);i++)
            {
                if(len%i==0)
                {
                    tmp=(tmp+i*1LL*lpb[i]);
                    if(i*i!=len)
                    tmp=(tmp+(len/i)*1LL*lpb[(len/i)]);
                }
            }
            ans=(ans*qpow(tmp,times))%mod;
        }
        printf("Case #%d: ",++cas);
        printf("%lld\n",ans);
    }
    return 0;
}