计算xor为零的整数分区

Question

我在寻找一种有效的方法来计算xor为零的整数分区数： F（n，c）=＃{（x1，x2， ...，xc）| X1 + X2 + ... + XC = N & X1 XOR X2 XOR ... XOR XC = 0}

对于N和C的值小，可以很容易地运行嵌套的循环来计算这些值。但是对于更大的价值来说，这并不容易处理。 我想获得一个封闭的表格或至少一个允许动态编程的递归公式..

Answer 1

除非你的问题的约束导致一个特别聪明和非常不明显的解决方案，我相信你问的一个非常困难的问题将处于研究数学领域的状态。首先，计算一个整数的普通无限制分区（也就是说，统计表示整数为正整数之和的可区分的，与顺序无关的方法的数量）是一个具有数百年历史的深刻数学问题旧。

http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Partition_function_formulas

你有一些额外的非常规的约束---第一，你只想与术语的给定数量的分区的子集（也可能更容易），然后是，我想，约束在术语的二进制表示的XOR上，这可能是非常难以处理的。

你打算有多大？上面的参考文献说p（1000）大约是2.44 * 10^31。

如果n很大，你是否也相信c会很小？这将大大简化事情。

为了解决您的问题，您需要引入专门研究该领域的研究数学家的兴趣。

www.aimath.org/news/partition/

你可能会使用“分区”作为关键字尝试数学溢出。

我发现这个线程关于分割成完全c（它们使用'k'这个部分）个别部分，这是你的第一个（更容易）约束。

https://mathoverflow.net/questions/72418/what-are-the-best-known-bounds-on-the-number-of-partitions-of-n-into-exactly-k