方幂圈问题

无心人

不合适的 我的算法时间复杂度几乎是线性的呢 你说的算法是O(n^3)的 mathe的要求的空间复杂度是O(n^2)的 17位以下的我都求出来了 你求取个18位的测试下你的想法吧 ============================ 根据你的思路，我也有了新想法 也许不用大数运算更好

medie2005

你说的算法是O(n^3)的 ==================== 如果是这样的话,Floyd会从棺材里跳出来的.

无心人

反正俺不懂那个 ========================== 我说下我的想法 标志1，圈上的某数 标志0，未处理数 标志-1，已处理数 标志2，临时标号 对数字映射\P -> R 测试P的标号，如果不是0跳过 如果P = R直接标号1，表示是长度1的圈，即黑洞数 否则，测试R标号，如果R标号是1或者-1，F 标号-1，转下一个数字 否则迭代计算P -> R, ，且记录下当前位置，并对路径上数字标号2，直到遇到R标号不是0 如果最终R标号是1或者-1，则对记录的所有数字标-1，继续转最开始的数字的下个数字 如果最终R标号是2，则找到一个圈上数字，标R标号是1，并标所有路径其他数字-1 输出所有标号是1的数字，并计算其代表的圈

无心人

media2005或者mathe能说下如何算编号和具体数列的对应关系么？ 编号从0开始 序列是递降序列，每项的范围9..1 序列长度是n

无心人

我想，可以做到每项2个比特 所以，还是能算到N = 32的

medie2005

我其实已经告诉你了: "编号从0开始,序列是递降序列，每项的范围9..1,序列长度是n"的所有的序列个数是C(n+8,n). 因此,我们只要知道两件事: 1): 如何把多重组合映射到元素值单一的组合 2): 对元素值单一的组合,怎么将编号和对应组合联系起来. 问题2)很简单. 对从1...n中选m个的某个组合a1,a2,a3,...,am,其对应序号是 C(a1-1,1)+C(a2-1,2)+...+C(am-1,m) . [定义n

无心人

知道单向映射的就足够了 另外，这个问题不是那么简单的

medie2005

问题1): 对从1...n中选m个的多重组合a1,a2,a3,...,am,1<=ai<=ai+1<=n 我们对每个ai加上i-1,显然,经过这样的操作之后,得到的序列是元素值单一的组合了. 这个新的组合的最大元素是多少?显然是n+m-1. 因此,总的个数就是这个新的组合的个数.即:C(n+m-1,m).

无心人

我很笨 这么做的情况下 如何映射到序号？

medie2005

先把多重组合映射为元素值单一的组合,然后由66#的公式就可以计算出对应的序号了.