首页 > ACM题库 > HDU-杭电 > HDU 3479-Code-组合数学-[解题报告]HOJ
2014
04-04

HDU 3479-Code-组合数学-[解题报告]HOJ

Code

问题描述 :

A new code system was designed recently. It works in the following way:
The original code A is a linear sequence containing N elements. Each element is an integer between 1 and N. At first the code system will generate a permutation B of length N automatically. Compare sequence A and B we can compute a hidden code C by the following rule:

Catch

where, B-11 stands for the location of integer i in permutation B. For example, if B = {3, 1, 2}, we have B-11=2,B-13=1 .
The code system has many great advantages in security. For instance, hackers will not have any idea about the original code A if he only gets the hidden code C. Considering all of these, we ordered one of the code systems.
However, some awful thing happened yesterday, the boss totally forgot his original code! The boss has the record of his hidden code, and he wants to ask you if it’s possible for him to find the original code soon.
More exactly, your task is to count the number of possible original codes that may generate the hidden code C by some permutation B.

输入:

The input contains multiple test cases.
In the first line of the input there’s an integer T which is the number of test cases. Then the description of T test cases will be given.
For each test case there will be two lines. The first line contains one integer N (≤ 30) which is the length of the hidden code C. The second line contains N integers between 1 and N giving C.

输出:

The input contains multiple test cases.
In the first line of the input there’s an integer T which is the number of test cases. Then the description of T test cases will be given.
For each test case there will be two lines. The first line contains one integer N (≤ 30) which is the length of the hidden code C. The second line contains N integers between 1 and N giving C.

样例输入:

3
5
1 2 3 4 5
5
2 2 2 2 2
5
3 2 5 2 2

样例输出:

Case 1: 1
Case 2: 5
Case 3: 120

题目链接于:

      http://acm.hdu.edu.cn/showproblem.php?pid=3479

       好久没写解题报告了,早一阵子和队友一起做了很多练习赛,我感觉自己做组合计数题的能力比去年退步。所以最近一直在补习组合数学。

      这个题是我今年做过的的最麻烦的组合数学,至少对我而言是很难的,我代码7000多B,260行,不知道那两位PE的神牛1600多B是怎么写的

     这个题的思路是这样的,首先要把题目条件归约为一个图,题目中核心的条件Code按照题目中给出的定义,这个式子等价于B[C[i]]=A[B[i]],其中C[i]是已知的,i呢,当然也已知,是我自己在枚举i。所以,可以写作A[B[i]]=B[j],其ij已知。因为B是一个全排列,所以A[B[i]]=B[j]就相当于给A中的每一个元素都指定了确切的值,只要B被确定,数组A就是唯一的。

                                                      Code 我们把B看做是一组节点,A是连接这些节点的
有向边,A[B[i]]=B[j]代表B[i]–>B[j]有边相连,以样例二为例,可以把A和B看成一个这样的图:

      数组B所代表的是图中的节点,而数组A代表的是边,题目的问题是如果B取遍1–n的所有全排列的值,会出现多少个不同的A?

       B是一个任意的排列,而我们要求的是A。不妨把B看做是不动的,从1—n排好了,而A,也就是这些边,可以随便动。怎样动才算符合要求呢?动完之后的图要和原图同构,只有同构才能够找到一组B,使这些A的变换等价于B的变换。

      由古怪的数组定义的题目终于变成了简单明了的形式:给出一个图,问有多少个图与原图同构。

     这个奇怪的问题我想了好久,其实就是用Burnside引理,其实我对Burnside的理解一直是一知半解的程度,只会原样套公式,导致这题卡了很久。这个题仅仅做了一个极小的转化。

       Burnside一般是用于求实质不同的方案数目的,但这里如果把我们要求的那么多图,说成是实质不同的方案,确实没有道理。我们要求的图应该算作表面不同的方案,而实质不同的方案,应该是指不同构的方案才对。这里我们要求的所有图都同构,所以实质不同的方案数就是1。

       置换的总数显然是N!,因为这对应于,把指向一个的节的边以及从这个的节出发的边看成一个整体,可以作为整体和其他的节点交换。

        因为已知的实质不同的方案数,可以列一个方程求表面不同的方案数:

         Sigma(0<=i<N!,在第i个置换下不变的与原图同构的图的数量)/N!=1;

        当然,如果我们设表面不同的方案数(即题目要求的与原图同构的图的数量)为x,也可以列如下方程:

         Sigma(0<=i<x,不能使第i个图发生变化的置换数量)/N!=1;

         方程就是这样的了。然后我们要观察到,我们所要统计的的所有的图都是同构的,所以不能使第i个图发生变化的置换数量,与不能使第j个图发生变化的置换数是一定会相同的。

        因此我们只需要统计某一个图(不妨就设原图,假设B就是从1–n的升序排列),不能使这个图发生变化的置换数量即可,假设它为r,则可通过方程(x*r)/N!=1算出x=N!/r;

       题目的思路到此以差不多完了,接下来是非常恐怖的编码设计,仅仅喜欢思路的读者可以不看了。

      考虑的这个图的特征,这个图可分为一些连通分量,每个联通分量有且只有一个环,每个节点出度都为1,所以这个图就是一个中间一个环,环上连了很多小树的形状。

     这里大量的用到树同构,树同构我还没怎么写过,代码很挫

     分三种情况讨论,什么样的置换是没有效果的:

      1、对于叶子节点,显然只要两个节点的父节点相同,就可以交换。同理对于子树中的节点,如果两个树的父节点相同,并且这两棵树本身同构,则可把这两棵树作为整体交换。如果k棵树可以相互交换,则置换总数乘以k的阶乘;

      2、环上的节点,考虑环可以转动的情况,如果转过之后,每个新位置上的节点都与旧节点完全相等,则这种转法对图没有影响。如果有k个位置可以转,则置换数乘以k;

      3、两个环相互同构(两环之间是不联通的,每个联通分量只有一个环),可以枚举一个环转动,看看能否匹配上,同样也是每个对应的节点为根的树同构才算环同构。如果k个环同构,则置换总数乘以k的阶乘;

      代码就是如此了,求出这种不使原图改变的置换总数r,然后N!/r就是程序输出的答案。还要用高精度,最大答案30!会超__int64

      这题样例数据PE,要AC极为困难,我PE了20多次才A,就是输出的冒号之前需要一个空格,想A的同学小心了

     

参考:http://hi.baidu.com/spellbreaker/item/4c8d905a478b5e12da163593


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。