c++ - 如何在不使用蛮力的情况下找到多少个没有前导零的数字（字符串 S）的排列可以被 11 整除？

Question

假设您有一个字符串S = {2,0,9,0}。满足条件的值为2009、 2090、2900、9002、9020和9200（S = {2,0,9,0} 的所有排列）。其中，只有 2090 和 9020 满足第二个条件（可被 11 整除），因此 S = {2,0,9,0} 的答案为2。

如果字符串 S 可以达到 100 位怎么办？蛮力永远不会结束。

提前致谢。

Answer 1

蛮横的，有n！要考虑的字符串。

如果我们注意到一个数字的重要之处在于它是处于奇数还是偶数位置，这会将它减少到 n!/(n/2)！² .

然后我们记住，可能的数字并不多。我们可以计算每个数字有多少，然后我们所要做的就是将每个数字的所有可能分区迭代到两个箱中（奇数和偶数位置）。这是昂贵的，但并非完全难以解决。

如果字符串真的很大，有数千位，那么值得考虑这样一个事实，即任何一个 bin 中的 11 个相同数字都等于没有，但是对于只有 100 个数字，这可能不值得付出努力。

一旦我们验证某个分区对应的数字可以被 11 整除，我们就可以计算有多少种方法将一个 bin 中的所有数字排列到所有可用位置，即 O(1)。