計算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