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

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

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

分析:

题目大意:

给你一个数组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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

2132
来自专栏杨建荣的学习笔记

Java随机数算法(一)(r11笔记第14天)

问:如何生成一个随机的字符串?答:让新手退出VIM 。 这可能也是随机字符的一种由来:) 我们今天要说的是随机数算法,这个我策划了好久,但是进展缓慢。...

4247
来自专栏IT可乐

由HashMap哈希算法引出的求余%和与运算&转换问题

1543
来自专栏数据小魔方

左右用R右手Python9——字符串合并与拆分

在文本处理和数据清洗阶段,对字符串或者字符型变量进行分割、提取或者合并虽然谈不上什么高频需求,但是往往也对很重要的。 接下来跟大家大致盘点一下在R语言与Pyh...

3455
来自专栏玄魂工作室

Python数据结构与算法-在M个数中找K个最小的数

比如输入10,-9,0,100,90,1,4,-9;找到最小的3个数为:-9,-9,0

2061
来自专栏算法修养

CodeForces 19D Points (线段树+set)

D. Points time limit per test 2 seconds memory limit per test 256 megabyte...

3669
来自专栏灯塔大数据

每周学点大数据 | No.22 外排序

No.22期 外排序(一) Mr. 王:接下来我们看一看在磁盘算法中一个比较典型的例子——外排序。 小可:那什么又是外排序呢? Mr. 王:外排序是相...

3606
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第12章 pandas高级应用12.1 分类数据12.2 GroupBy高级应用12.3 链式编程技术12.4 总结

前面的章节关注于不同类型的数据规整流程和NumPy、pandas与其它库的特点。随着时间的发展,pandas发展出了更多适合高级用户的功能。本章就要深入学习pa...

6517
来自专栏塔奇克马敲代码

不相交集类

3385
来自专栏ml

位运算的方法,小结

文章来源未知----再次声明为转载... 本文是针对使用位运算来实现一些方法,我们都知道位运算的代价比其他符号运算都低,所以当一个方法只使用位运算且运算次数与其...

37213

扫码关注云+社区