2017 Multi-University Training Contest - Team 1 1006&&HDU 6038 Function【DFS+数论】-阿里云开发者社区

开发者社区> 大数据> 正文

2017 Multi-University Training Contest - Team 1 1006&&HDU 6038 Function【DFS+数论】

简介: Function Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 652    Accepted Submission(s): 267...

Function

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


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
分析:

题目大意:


给你一个数组A,和一个数组B,数组A是【0~n-1】的排咧,数组B是【0~m-1】的排列。

现在定义F(i)=bF(ai);

问有多少种取值,使得F(i)全部合法。

样例1可行的解:

110

111

001

000


分析:

写出样例2的公式:


①F(0)=bF(2)

②F(1)=bF(0)

③F(2)=bF(1)


我们不难发现,如果我们设定了F(0)的值,就能够通过式子②能够得知F(1)的值,然后就能通过式子③得知F(2)的值,最后再回归式子①尝试当前设定的值是否合法了。


这就是一个循环节


我们对于A数组中的一个环的话如果一个环中的任意一个点的价值我们能够设定出来,那么这一个循环节的所有点的值就都能够知道了。

然而这个能够设定的值,肯定是数组B中的一个值,而且我们已知都是循环节,那么数组B中的这个被选中设定的值也一定存在一个循环节,而且这个循环节的长度,一定是A长度循环节的因子长度。


A数组中长度为D的一个循环节,如果B数组中有一个循环节的长度为d,并且如果D%d==0.那么这个B数组的这个循环节的所有值,都可以作为A数组中这个循环节的值。那么对于A数组中的这个循环节来讲,答案数就多了d个。

过程统计每个循环节能够满足的答案的个数,然后累乘即可。

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=100010;
 4 const int mod=1000000007;
 5 int n,m,ans=1;
 6 int a[maxn],b[maxn];
 7 int cal[2][maxn];
 8 bool vis[maxn];
 9 inline void DFS(int t,int l,int *a,int k)
10 {
11     if(vis[t])
12     {
13         cal[k][l]++;
14         return;
15     }
16     vis[t]=1;
17     DFS(a[t],l+1,a,k);
18 }
19 int main()
20 {
21     int tcase=1;
22     while(scanf("%d%d",&n,&m)!=EOF)
23     {
24         for(int i=0;i<n;i++)
25             scanf("%d",&a[i]);
26         for(int i=0;i<m;i++)
27             scanf("%d",&b[i]);
28         memset(cal,0,sizeof(cal));
29         memset(vis,false,sizeof(vis));
30         for(int i=0;i<m;i++)
31         {
32             if(!vis[i])
33                 DFS(i,0,b,0);
34         }
35         memset(vis,false,sizeof(vis));
36         for(int i=0;i<n;i++)
37         {
38             if(!vis[i])
39                 DFS(i,0,a,1);
40         }
41         ans=1;
42         for(int i=1;i<=n;i++)
43         {
44             if(cal[1][i])
45             {
46                 int lim=(int)sqrt(i+0.5);
47                 int ta=0;
48                 for(int j=1;j<=lim;j++)
49                 {
50                     if(i%j==0)
51                     {
52                         (ta+=(long long)cal[0][j]%mod*j%mod)%=mod;
53                         if(j*j!=i)
54                             (ta+=(long long)cal[0][i/j]%mod*(i/j)%mod)%=mod;
55                     }
56                 }
57                 for(int j=1;j<=cal[1][i];j++)
58                 {
59                     ans=(long long)ans*ta%mod;
60                 }
61             }
62         }
63         printf("Case #%d: %d\n",tcase++,ans);
64     }
65     return 0;
66 }

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
大数据
使用钉钉扫一扫加入圈子
+ 订阅

大数据计算实践乐园,近距离学习前沿技术

其他文章