排列组合，BigInteger, 优化排列

解题思路:

要求分割两个子集，其中一个可以为空集，且两个集合为偶数，所有第一步判断集合的总和是否为偶数，如果不为偶数则直接判定为 0 个否则再进行深度收搜判断 (暴力超时)

也可以利用奇数个数与偶数个数的排列组合实现， 将两个奇数拼接为一个偶数，判断无重复的奇数拼接情况，与偶数个数相加，递推排列组合公式  (正解)

优化排列组合，会发现是高精度算法 设 x 为偶数个数， y 为奇数个数ans = pow(x + (y == 0 ? 0 : y - 1)) % mod 算法标签：递推，找规律，贪心

注意事项:
 x + (y == 0 ? 0 : y - 1), 奇数为0情况

```

参考代码:

//排列组合递推公式

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
    public static final BigInteger MOD = new BigInteger("1000000007");
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T-- > 0){
            int n = scan.nextInt();
            int[] a = new int[n];
            long x = 0, y = 0; // x 记录偶数， y 记录奇数
            for(int i = 0; i < n; i++){
                a[i] = scan.nextInt() % 2;
                if(a[i] == 0){
                    x++;
                }else {
                    y++;
                }
            }
            if(y % 2 == 1){ // 奇数个数为奇，没有一个条件成立
                System.out.println(0);
                continue;
            }
            x = x + (y == 0 ? 0 : y - 1);  // 两个奇数组合为一个偶数，排除重复情况
            BigInteger ans = new BigInteger("2");
            BigInteger dp = new BigInteger("1");
            // C(n,m) = P(n,m) / P(m,m) = n! / m! * (n - m)!
            // 转移递推公式 dp = (dp * (x, x-1, x-2, ... , n) / (1, 2, 3, ... , n))
            for(long i = 1, j = x; i < x; i++, j--){ // 排列组合无顺序 C
                BigInteger u = new BigInteger(String.valueOf(j));
                BigInteger v = new BigInteger(String.valueOf(i));
                dp = dp.multiply(u).divide(v);
                ans = ans.add(dp);
            }
            System.out.println(ans.mod(MOD));
        }
    }
}







//优化高精度

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
    public static final BigInteger MOD = new BigInteger("1000000007");
    public static final BigInteger TWO = new BigInteger("2");
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T-- > 0) {
            int n = scan.nextInt();
            int x = 0, y = 0; // x 记录偶数， y 记录奇数
            for (int i = 0; i < n; i++) {
                int a = scan.nextInt() % 2;
                if (a == 0) {
                    x++;
                } else {
                    y++;
                }
            }
            if (y % 2 == 1) {
                System.out.println(0);
            }else{
                System.out.println(TWO.pow(x + (y == 0 ? 0 : y - 1)).mod(MOD));
            }
        }
    }
}