青训营 X 豆包MarsCode 技术训练营--二分数字

问题描述

给定一个数组，请你把数组里的数字分为两组，使一组数字和的个位数等于 A（1 ≤ A ≤ 9），且剩余数字和的个位数等于 B（1 ≤ B ≤ 9）；或者一组数字的个数为零，但剩余数字和的个位数等于 A 或 B。请问一共有多少种划分方式？

备注：

1. 数组里的数字可以相等，但每个数字都是独一无二的。
   比如数组 a 等于[1, 1, 1]，A 等于 1，B 等于 2，则一共有三组划分方式：
   第一种：
   A：a[0]
   B：a[1]、a[2]
   第二种：
   A：a[1]
   B：a[0]、a[2]
   第三种：
   A：a[2]
   B：a[0]、a[1]

2. 可以将所有数字都划分到同一组，使其和的个位数等于 A 或 B；另一组为空
   比如数组 a 等于[1, 1, 1]，A 等于 3，B 等于 5，则共有一组划分方式：
   A：a[0]、a[1]、a[2]
   B：空

输入格式

输入第一行包含三个整数 n、A、B（1 ≤ n ≤ 100000，1 ≤ A ≤ 9，1 ≤ B ≤ 9），n 代表需要数组中的数字个数。

第二行，有 n 个元素，代表数组内的数字（1 ≤ 每个数字 ≤ 9）。

输出格式

输出一共有多少种划分方式，结果对 10000007 取余。

输入样例

样例 1

3 1 2

1 1 1

样例 2

3 3 5

1 1 1

样例 3

2 1 1

1 1

输出样例

样例 1

3

样例 2

1

样例 3

2

代码

public class Main {
public static int solution(int n, int A, int B, int[] array_a) {
// 初始化结果为 0
int count = 0;
// 遍历数组的所有子集
for (int mask = 0; mask < (1 << n); mask++) {

    (1 << n) 表示 2 的 n 次方，即数组所有可能的子集数量。
每个元素可以有两种状态：要么属于 A 组，要么属于 B 组。
对于一个包含 n 个元素的数组，每个元素都有两种选择，因此总共有 2n2n 种不同的组合方式。

int sumA = 0;
int sumB = 0;
// 计算每个子集对应的两组数字之和
for (int i = 0; i < n; i++) {
if ((mask & (1 << i))!= 0) {
sumA += array_a[i];
} else {
sumB += array_a[i];
}
}
// 检查和的个位数是否符合要求
if ((sumA % 10 == A && sumB % 10 == B) || (sumA == 0 && sumB % 10 == A) || (sumB == 0 && sumA % 10 == B)) {

(sumA % 10 == A && sumB % 10 == B)：A 组的和的个位数等于 A 且 B 组的和的个位数等于 B。
(sumA == 0 && sumB % 10 == A)：A 组为空且 B 组的和的个位数等于 A。
(sumB == 0 && sumA % 10 == B)：B 组为空且 A 组的和的个位数等于 B。count++;}}// 返回结果并取模return count % 10000007;
}public static void main(String[] args) {// 您可以在此添加更多测试用例int[] array1 = {1, 1, 1};int[] array2 = {1, 1, 1};int[] array3 = {1, 1};System.out.println(solution(3, 1, 2, array1) == 3);System.out.println(solution(3, 3, 5, array2) == 1);System.out.println(solution(2, 1, 1, array3) == 2);
}

}