数组创建为数字时有多少种排列可以被 4 或 8 整除？

Question

我们有一个数字数组，例如。 {0,5,4,8,9}。我们必须找到当数组转换为数字时（例如 {6, 8, 3, 2} -> 6832）该数字能被 4 整除的排列数。向量的元素数为最大限度。 17 所以我只需要找到一个指数算法。 我尝试了很多不同的方法，并决定寻找“成对”的数字，但我感兴趣的是，是否有一种不那么破坏理智的方法也适用于前任。能被 8 整除的数字。

Answer 1

一个数字可以被八整除当且仅当它的最后两位数字形成的数字可以被八整除。

假设你的数组 A 的大小为 n。

1. 数出能被 4 整除的 2 位以上的数字。假设这是 k。任何一个最后都会得到一个能被 4 整除的数字，所以这些贡献了 k * (n-1)！到总数。

2. 如果有偶数1位数字

2a。计算与 0 mod 4 全等的 1 位数字。

2b。计算与 2 mod 4 全等的 1 位数字。

2c。数出所有偶数

2d。请注意，n -（偶数的数量）是奇数的数量。

2e。添加（n-2）！ * (2a * 2c) 总计。

2f。添加（n-2）！ * (2b * 2d) 总计。

这是有效的，因为最后一位数字 d 的有效前任是：

if d mod 4 is 0: 0, 2, 4, 6, 8
if d mod 4 is 2: 1, 3, 5, 7, 9
otherwise: n/a

在你的例子中[0,5,4,8,9]：

0：没有2位以上数字 2a.有 3 个数字与 0 mod 4 一致：0, 4, 8 2b.有 0 个数字与 2 mod 4 全等 2c：有 3 个偶数：0、4、8 2d：有 2 个奇数：5、9

这里，我们的总数是 0 + 6 * 3 * 3 + 6 * 0 * 2 = 54