1

我正在寻找一种有效的方法来计算异或为零的整数分区数: F(n,c) = #{ (x1,x2, ... ,xc) | x1 + x2 + ... + xc = n & x1 xor x2 xor ... xor xc = 0 }

对于 n 和 c 的小值,很容易运行嵌套循环来计算这些值。但是对于较大的值,它是不可处理的。我想获得一个封闭的形式或至少一个允许动态编程的递归公式..

4

1 回答 1

1

除非您的问题的约束导致一个特别聪明且非常不明显的解决方案,否则我相信您会问一个非常困难的问题,该问题将处于研究数学的最新水平。

首先,只计算一个整数的普通无限制分区(即计算将整数表示为正整数之和的可区分、与顺序无关的方法的数量)是一个有着数百年历史的深刻数学问题。

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)单个部分,这是你的第一个(更简单的)约束。

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

于 2011-11-22T09:39:06.143 回答