求数组排列构成的数能被4或8整除的排列数量

核心思路：用整除规则拆解问题 #

判断4或8的整除性，都可以通过末尾固定长度的数字组合快速筛选，再结合多重集合排列公式计算合法数量。注意：能被8整除的数必然能被4整除，因此「能被4或8整除」等价于「能被4整除」；若需要分别统计两者的数量，只需单独计算后用容斥去重即可。

具体步骤 #

1. 预处理数字频率

统计数组中0-9每个数字的出现次数，用freq[0...9]数组存储，方便后续判断是否能组成目标末尾串。

2. 通用计算逻辑（同时适配4和8）

针对除数m（4对应检查末尾2位，8对应检查末尾3位）：

• 枚举所有长度为k（k=2或3）的数字组合（允许前导零，因为是末尾部分），筛选出数值能被m整除的组合。
• 对每个符合条件的组合：
  • 校验数组中是否有足够数字组成该组合（比如组合是[8,8]，则需要freq[8]>=2；组合是[4,8]则需要freq[4]>=1且freq[8]>=1）。
  • 计算剩余数字的排列数：用多重集合排列公式，剩余数字总个数为n - k，排列数为 (n-k)! / (Π (freq[d] - cnt[d])! )，其中cnt[d]是该组合中数字d的出现次数。
  • 排除前导零无效排列：若剩余数字全为0（即n-k > 0且非零数字剩余次数均为0），这种排列会产生前导零，需从结果中减去该情况的排列数（通常为1）。

3. 处理「或」的逻辑

由于8是4的倍数，所有能被8整除的排列已包含在能被4整除的结果中，因此「能被4或8整除」的总数量直接等于能被4整除的排列数。若需分别统计两者数量，单独计算后相加再减去重复部分（即能被8整除的数量）即可。

示例计算（以数组{0,5,4,8,9}为例） #

计算能被4整除的排列数：

• 枚举所有能被4整除的两位组合，比如04、40、08、48、80、84等。
• 以组合48为例：数组中有1个4和1个8，剩余数字为0、5、9，排列数为3! = 6。
• 以组合04为例：剩余数字为5、8、9，排列数为3! =6，剩余数字无全0情况，无需额外扣除。
• 累加所有符合条件组合的排列数，即为最终结果。

优化点 #

• 预先生成所有符合条件的末尾组合（比如4的两位合法组合共25种：00、04、08...96），避免全量枚举100或1000种情况。
• 提前计算阶乘（17!约为3.5e14，可用64位整数存储），减少重复计算。

内容的提问来源于stack exchange，提问作者K123