Function
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 273 Accepted Submission(s): 99
Define that the domain of function f is the set of integers from 0 to n−1, and the range of it is the set of integers from 0 to m−1.
Please calculate the quantity of different functions f satisfying that f(i)=bf(ai) for each i from 0 to n−1.
Two functions are different if and only if there exists at least one integer from 0 to n−1 mapped into different integers in these two functions.
The answer may be too large, so please output it in modulo 109+7.
For each case:
The first line contains two numbers n, m. (1≤n≤100000,1≤m≤100000)
The second line contains n numbers, ranged from 0 to n−1, the i-th number of which represents ai−1.
The third line contains m numbers, ranged from 0 to m−1, the i-th number of which represents bi−1.
It is guaranteed that ∑n≤106, ∑m≤106.
1 0 2
0 1
3 4
2 0 1
0 2 3 1
Case #2: 4
/*
* @Author: Lyucheng
* @Date: 2017-07-25 15:25:56
* @Last Modified by: Lyucheng
* @Last Modified time: 2017-07-25 20:42:28
*/
/*
题意：给你两个序列，定义一种函数 f(i)=b[f(ai)] ，问你已给出的序列可以构造出的函数的数量 思路：实际上就是从a集合到b集合的映射的组合，a中的一个循环节是一个整体，如果b中循环节的长度和a循环节的长度相同
或者是因子，那么就可以置换过来，满足这个条件，将结果组合一下就好 感悟：好气啊，想出来，但是没想到因子这个条件...
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h> #define MAXN 100005
const long long MOD = 1e9+;
#define LL long long
using namespace std; int n,m;
int a[MAXN];
int b[MAXN];
bool visa[MAXN];
bool visb[MAXN];
vector<int> va;
vector<int> vb;
int ca=; void init(){
va.clear();
vb.clear();
memset(visa,false,sizeof visa);
memset(visb,false,sizeof visb);
memset(a,,sizeof a);
memset(b,,sizeof b);
} int main(){
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(scanf("%d%d",&n,&m)!=EOF){ init();
for(int i=;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=;i<m;i++){
scanf("%d",&b[i]);
} for(int i=;i<n;i++){//求A的循环节
if(visa[i]==true) continue; int cur=;
int x=a[i];
while(x!=a[x]){
if(visa[x]==true) break;//走到了标记过的点 可能遇到没返回自己的循环了，也可能返回自己了
visa[x]=true;
cur++;
x=a[x];
}
if(x==a[i]){
if(cur==)
va.push_back();
else
va.push_back(cur);
}else{
va.push_back();
int cnt=;
while(x!=a[x]){
cnt++;
if(cnt>=cur) break;
visa[x]=false;
x=a[x];
}
visa[a[i]]=true;
}
} for(int i=;i<m;i++){//求B的循环节
if(visb[i]==true) continue; int cur=;
int x=b[i];
while(x!=b[x]){
if(visb[x]==true) break;//走到了标记过的点 可能遇到没返回自己的循环了，也可能返回自己了
visb[x]=true;
cur++;
x=b[x];
}
if(x==b[i]){
if(cur==)
vb.push_back();
else
vb.push_back(cur);
}else{
vb.push_back();
int cnt=;
while(x!=b[x]){
cnt++;
if(cnt>=cur) break;
visb[x]=false;
x=b[x];
}
visb[b[i]]=true;
}
} LL res=;
for(int i=;i<va.size();i++){
LL cur=;
for(int j=;j<vb.size();j++){
if(va[i]%vb[j]==){
cur+=( (LL)(vb[j]) ) %MOD;
cur%=MOD;
}
}
res=( (res%MOD) * (cur%MOD) )%MOD;
} printf("Case #%d: %d\n",ca++,res);
}
return ;
}