计算异或为零的整数分区
我正在寻找一种有效的方法来计算异或为零的整数分区数： F(n,c) = #{ (x1,x2, ... ,xc) | F(n,c) = #{ (x1,x2, ... ,xc) | x1 + x2 + ... + xc = n & x1 xor x2 xor ... xor xc = 0 }
对于 n 和 c 的小值，很容易运行嵌套循环来计算这些值。但对于较大的值，则不太容易处理。 我想获得一个封闭形式或至少一个允许动态编程的递归公式。
I'm looking for an efficient way to compute the number of partitions of integer for which the xor is zero:
F(n,c) = #{ (x1,x2, ... ,xc) | x1 + x2 + ... + xc = n & x1 xor x2 xor ... xor xc = 0 }
For little values of n and c, it's easy to run nested loops to compute those values. But for larger values, it's not tractable.
I'd like to obtain a closed form or at least a recursive formula which allow dynamic programming..
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
除非你的问题的限制导致一个特别聪明和非常不明显的解决方案，否则我相信你正在问一个极其困难的问题，这将是研究数学的最新技术。
首先，计算整数的普通无限制分区（即计算将整数表示为正整数之和的可区分的、与顺序无关的方式的数量）是一个具有数百年历史的深层数学问题。
http://en.wikipedia.org/wiki/Partition_%28number_theory%29# Partition_function_formulas
您还有一些额外的非正统约束——首先，您只需要具有给定数量项的分区子集（即可能会更容易），然后，我认为，对术语的二进制表示的异或的约束，这可能很难处理。
你打算n多大？上面的参考文献说 p(1000) 大约为 2.44 * 10^31。
如果n很大，你是否也相信c会很小？这将大大简化事情。
为了解决您的问题，您需要引起专门从事该领域的研究数学家的兴趣。
www.aimath.org/news/partition/
您可以使用“Partitions”作为关键字来尝试 Math Overflow。
我发现这个线程关于精确划分为 c （他们在这部分使用“k”）各个部分，这是你的第一个（更容易的）约束。
<一href="https://mathoverflow.net/questions/72418/what-are-the-best-known-bounds-on-the-number-of-partitions-of-n-into-exactly-k">https： //mathoverflow.net/questions/72418/n-into-exactly-k 的分区数量的最佳已知边界是什么
Unless your problem's constraints lead to a particularly clever and very unobvious solution, I believe you are asking an exceedingly difficult question which would be at the state of the art of research mathematics.
First, counting just plain unrestricted partitions of an integer (that is, counting the number of distinguishable, order-independent ways of representing an integer as a sum of positive integers) is a deep mathematical problem with a history hundreds of years old.
http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Partition_function_formulas
You have some additional unorthodox constraints---first that you only want the subset of partitions with a given number of terms (that may make it easier), and then that, I presume, a constraint on the XOR of the binary representation of the terms, which would probably be very difficult to handle.
How big do you intend n to be? The reference above says that p(1000) is roughly 2.44 * 10^31.
If n is big, do you also believe that c will be small? That would greatly simplify things.
To solve your problem you need to engage the interest of a research mathematician specializing in this field.
www.aimath.org/news/partition/
You might try Math Overflow using "Partitions" as a keyword.
I found this thread about partitioning into exactly c (they use 'k' for this part) individual parts, which is the first (easier) constraint of yours.
https://mathoverflow.net/questions/72418/what-are-the-best-known-bounds-on-the-number-of-partitions-of-n-into-exactly-k