方幂圈问题

无心人

不合适的

我的算法时间复杂度几乎是线性的呢
你说的算法是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<m时,C(n,m)=0].
问题1)也不难,你自己想想.

无心人

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

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#的公式就可以计算出对应的序号了.