HDU 6038 Function（找规律）——2017 Multi-University Training Contest - Team 1

传送门

Function

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1034    Accepted Submission(s): 464

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

题目大意：

给定两个数列 a 和 b， 求有多少个 f 映射满足： f(i)=bf(ai)

解题思路：

其实题解说的很明白了，我就不在赘述了。

其实可以根据第二个样例找规律，然后大胆猜想，不用验证。

代码：

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+5;
const LL MOD = 1e9+7;
int vis[MAXN], A[MAXN], B[MAXN], a[MAXN], b[MAXN];
int get(int a[], int A[], int n){
    memset(vis, 0, sizeof(vis));
    int cnt = 0;
    for(int i=0; i<n; i++){
        int cur = a[i];
        if(!vis[cur]){
            while(1){
                if(vis[cur]) break;
                vis[cur] = 1;
                cur = a[cur];
                A[cnt]++;
            }
            cnt++;
        }
    }
    return cnt;
}
int main()
{
    int n, m, cas = 1;
    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<n; i++) scanf("%d", &a[i]);
        for(int i=0; i<m; i++) scanf("%d", &b[i]);
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        int cnta = get(a, A, n);
        int cntb = get(b, B, m);
        LL ans = 1;
        for(int i=0; i<cnta; i++){
            LL cnt = 0;
            for(int j=0; j<cntb; j++)
                if(A[i]%B[j] == 0) cnt += B[j];
            ans = ans * cnt % MOD;
        }
        printf("Case #%d: %lld\n",cas++,ans);
    }
    return 0;
}