CC

自然万物都趋向从有序变得无序

0%

Function HDU - 6038

发表于 更新于 分类于 Valine：

[题目链接](http://acm.hdu.edu.cn/showproblem.php?pid=6038)

题目

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 1e9+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.
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

题意:

给出两个序列 a 和 b ，求满足$ f(i)=b_{f(ai)}$ 的函数个数。

思路:

根据样例 1 我们可以得到：

f(0)=bf(1)f(0)=b_f(1)

f(1)=bf(0)f(1)=b_f(0)

f(2)=bf(2)f(2)=b_f(2)
这里写图片描述

官方题解很清楚

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int mod = 1e9+7;
const int maxn = 1e5 + 10;

int a[maxn],b[maxn];
bool vis[maxn];
vector<int> q1,q2;

int main(){
    int n, m;
    int kase = 0;
    while(scanf("%d %d", &n, &m) != EOF){
        for(int i = 0; i < n; ++i)
            scanf("%d", a+i);
        for(int i = 0; i < m ;++i)
            scanf("%d", b+i);
        printf("Case #%d: ", ++kase);
        memset(vis,false,sizeof(vis));
        q1.clear();
        q2.clear();
        for(int i = 0; i < n; ++i){
            int cur = i;
            int cnt = 1;
            if(vis[i]) continue;
            while(a[cur] != i){
                cur =a[cur];
                vis[cur] = true;
                ++cnt;
            }q1.push_back(cnt);
        }memset(vis,false,sizeof(vis));
         for(int i = 0; i < m; ++i){
            int cur = i;
            int cnt = 1;
            if(vis[i]) continue;
            while(b[cur] != i){
                cur =b[cur];
                vis[cur] = true;
                ++cnt;
            }q2.push_back(cnt);
        }int ans = 1;
        int len1 = q1.size();
        int len2 = q2.size();
        for(int i = 0; i < len1; ++i){
            int res = 0;
            for(int j = 0; j < len2; ++j)
                if(q1[i] % q2[j] == 0)
                    res = (res + q2[j]) % mod;
            ans = ans * res % mod;
        }printf("%d\n",ans);
    }return 0;
}