我正在寻找一种有效的方法来计算异或为零的整数分区数: F(n,c) = #{ (x1,x2, ... ,xc) | x1 + x2 + ... + xc = n & x1 xor x2 xor ... xor xc = 0 }
对于 n 和 c 的小值,很容易运行嵌套循环来计算这些值。但是对于较大的值,它是不可处理的。我想获得一个封闭的形式或至少一个允许动态编程的递归公式..
我正在寻找一种有效的方法来计算异或为零的整数分区数: F(n,c) = #{ (x1,x2, ... ,xc) | x1 + x2 + ... + xc = n & x1 xor x2 xor ... xor xc = 0 }
对于 n 和 c 的小值,很容易运行嵌套循环来计算这些值。但是对于较大的值,它是不可处理的。我想获得一个封闭的形式或至少一个允许动态编程的递归公式..
除非您的问题的约束导致一个特别聪明且非常不明显的解决方案,否则我相信您会问一个非常困难的问题,该问题将处于研究数学的最新水平。
首先,只计算一个整数的普通无限制分区(即计算将整数表示为正整数之和的可区分、与顺序无关的方法的数量)是一个有着数百年历史的深刻数学问题。
http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Partition_function_formulas
你有一些额外的非正统约束——首先你只想要具有给定数量的术语的分区子集(这可能会使它更容易),然后,我认为,对二进制表示的 XOR 的约束条款,这可能很难处理。
你打算 n 有多大?上面的参考资料说 p(1000) 大约是 2.44 * 10^31。
如果n很大,你也相信c会很小吗?这将大大简化事情。
要解决您的问题,您需要吸引专门从事该领域的研究数学家的兴趣。
www.aimath.org/news/partition/
您可以使用“Partitions”作为关键字来尝试 Math Overflow。
我发现this thread about partitioning into exact c (they use 'k' for this part)单个部分,这是你的第一个(更简单的)约束。