http://acm.hdu.edu.cn/showproblem.php?pid=6038
Function
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1680 Accepted Submission(s): 790
Problem Description
You are given a permutation
a
from
0
to
n−1
and a permutation
b
from
0
to
m−1
.
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
.
Input
The input contains multiple test cases.
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
.
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 of corresponding case.
Sample Input
3 2
1 0 2
0 1
3 4
2 0 1
0 2 3 1
Sample Output
Case #1: 4
Case #2: 4
Source
2017 Multi-University Training Contest - Team 1
题意：给出数组a和b，求满足方程f(i)=b[f(a[i])]的映射f个数。
题解：根据样例二：根据题意写出f(0)=b[f(2)]，f(1)=b[f(0)]，f(2)=b[f(1)]。然后用数组b对f(0)赋值，一旦确定f(0)其他两个就确定了。而要使得赋值不矛盾，我们选的b值的必须是循环节，而且它的循环节必须是f个数的因子。再看f是怎么来的，是从a数组得来，而样例二中a本身恰好就是一个循环节。若a的循环节不止一个，那么就会有多组上述的f，但是他们之间互不干扰。再回到b对f赋值，如果b满足了赋值条件，那么对于其中一个a的循环节，它的映射个数就是b的循环节相加。最后的答案就是a的每个循环节映射个数相乘。
代码：
#include<bits/stdc++.h>
#define debug cout<<"aaa"<<endl
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define MIN_INT (-2147483647-1)
#define MAX_INT 2147483647
#define MAX_LL 9223372036854775807i64
#define MIN_LL (-9223372036854775807i64-1)
using namespace std;
const int N = 100000 + 5;
const int mod = 1000000000 + 7;
int a[N],b[N],lena[N],lenb[N],n,m,cnta,cntb,cas=0;
LL ans,sum;
bool vis[N];
int get(int a[],int len[],int n){//求循环节个数及长度
mem(vis,0);
int cnt=0;
for(int i=0;i<n;i++){
int t=a[i],num=0;
if(!vis[i]){
while(!vis[t]){
vis[t]=1;
t=a[t];
num++;
}
len[cnt]=num;
cnt++;
}
}
return cnt;
}
int main(){
while(~scanf("%d%d",&n,&m)){
mem(lena,0),mem(lenb,0),ans=1;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<m;i++){
scanf("%d",&b[i]);
}
cnta=get(a,lena,n);
cntb=get(b,lenb,m);
for(int i=0;i<cnta;i++){
sum=0;
for(int j=0;j<cntb;j++){
if(lena[i]%lenb[j]==0){
sum+=lenb[j];//对于a的每个循环节，满足赋值条件的b的个数相加
}
}
ans=(ans*sum)%mod;//a的各循环节之间要相乘
}
printf("Case #%d: %lld\n",++cas,ans);
}
return 0;
}
Function
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1680 Accepted Submission(s): 790
Problem Description
You are given a permutation
a
from
0
to
n−1
and a permutation
b
from
0
to
m−1
.
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
.
Input
The input contains multiple test cases.
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
.
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 of corresponding case.
Sample Input
3 2
1 0 2
0 1
3 4
2 0 1
0 2 3 1
Sample Output
Case #1: 4
Case #2: 4
Source
2017 Multi-University Training Contest - Team 1
