首页 > 代码库 > HDU 6038

HDU 6038

2024-11-07 21:08:40   204人阅读

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
 

 

Source
2017 Multi-University Training Contest - Team 1
题意：
长度为n的数列a[0...n-1]和长度为m的数列b[0...m-1]，求有多少个这样的函数f使得 f(i)=bf(ai)，i属于[0,n-1];
代码：
//可以看出f在定义域[0,n-1]中是循环的，f的每个循环节中只要有一个f的值确定了那么其他的f的值也就确定了(//因为每相邻的两个f都相关)，所以先找出a数列的所有的循环节然后在b中找f可以对应的值(同样是循环节)，只有b//的某个循环节是a的某个循环节的因子时这两个循环节才能匹配，统计能匹配的个数，结果相乘。#include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef long long ll;const int maxn=100009;const ll mod=1e9+7;int n,m,a[maxn],b[maxn];int num1[maxn],num2[maxn];//num1[i]表示a数列第i个循环节的大小，num2[i]表示b数列长度为i的循环节的个数int main(){    int cas=0;    while(scanf("%d%d",&n,&m)==2){        for(int i=0;i<n;i++) scanf("%d",&a[i]);        for(int i=0;i<m;i++) scanf("%d",&b[i]);        memset(num2,0,sizeof(num2));        memset(num1,0,sizeof(num1));        int tot=0;        for(int i=0;i<n;i++){            if(a[i]==-1) continue;            int ii=i;            tot++;            while(a[ii]!=-1){                num1[tot]++;                int t=ii;                ii=a[ii];                a[t]=-1;            }        }        for(int i=0;i<m;i++){            if(b[i]==-1) continue;            int ii=i,len=0;            while(b[ii]!=-1){                len++;                int t=ii;                ii=b[ii];                b[t]=-1;            }            num2[len]++;        }        ll sum=1;        for(int i=1;i<=tot;i++){            ll cnt=0;            for(int j=1;j<=num1[i];j++){                if(num1[i]%j==0){                    cnt+=num2[j]*j;                    cnt%=mod;                }            }            sum*=cnt;            sum%=mod;        }        printf("Case #%d: %lld\n",++cas,sum);    }    return 0;}

 

 

HDU 6038


联系
我们