题目描述

【问题描述】
小蓝有一个长度为 N 的数组 A = [ A 0 , A 1 , . . . , A N − 1 ] 。现在小蓝想要从 A 对应的数组下标所构成的集合 I = { 0 , 1 , 2 , . . . , N − 1 } 中找出一个子集 R 1 ，那么 R 1在 I 中的补集为 R 2 。记 S 1 = ∑ r ∈ R 1 A r ， S 2 = ∑ r ∈ R 2 A r，我们要求 S 1 和 S 2 均为 偶数，请问在这种情况下共有多少种不同的 R 1。当 R1 或 R 2 为空集时我们将 S 1 或 S 2 视为 0。

【输入格式】
第一行一个整数 T ，表示有 T 组数据。 接下来输入 T 组数据，每组数据包含两行：第一行一个整数 N ，表示数组 A 的长度；第二行输入 N 个整数从左至右依次为 A 0 , A 1 , . . . , A N − 1 ，相邻元素之 间用空格分隔。
【输出格式】
对于每组数据，输出一行，包含一个整数表示答案，答案可能会很大，你
需要将答案对 1000000007 进行取模后输出。

题解

对于这道题目，我们发现答案是否存在跟偶数没啥关系，所以只有奇数的个数为奇数，那么这串数字肯定凑不出来偶数和，直接输出零即可。

我们把奇数跟偶数分开处理，我们发现这道题目实际上就是一个组合数，就是从数组里面能抽出来多少对奇数的组合个数跟多少对偶数。

因为组合数公式涉及到除法，除法不能直接取模，因此我们要用到逆元

$$\text{ Ans }=(C_{ji}^0+C_{ji}^2+\cdots +C_{ji}^{\left[\frac{ji}{2}\right]\ast 2})\ast (C_{ou}^0+C_{ou}^1+\cdots +C_{ou}^{ou})mod(1e9+7)$$

代码

用了快速幂求逆元

import java.util.*;

public class Main {

    static final int maxn = 1005;
    static final long mod = 1000000007;
    static int t, n;
    static int[] a = new int [maxn];
    static long[] fact = new long[maxn];
    static long[] inv = new long[maxn];

    static long power(long a, long b) {
        long res = 1;
        while (b > 0) {
            if (b % 2 == 1) {
                res = (res * a) % mod;
            }
            a = (a * a) % mod;
            b /= 2;
        }
        return res;
    }

    static void precompute() {
        fact[0] = inv[0] = 1;
        for (int i = 1; i < maxn; i++) {
            fact[i] = (fact[i - 1] * i) % mod;
            inv[i] = power(fact[i], mod - 2);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        t = sc.nextInt();
        precompute();
        while(t -- > 0) {
            n = sc.nextInt();
            a[0] = 0; // a[0] 用于记录数组中奇数数字个数
            for(int i = 1; i <= n; i ++) {
                a[i] = sc.nextInt();
                a[0] += a[i] % 2;
            }
            if(a[0] % 2 == 1) { // 奇数数字个数为奇数，无答案
                System.out.println(0);
                continue;
            }

            long ansj = 0, anso = 0;
            for(int i = 0; i <= n - a[0]; i++)
                anso = (anso + fact[n - a[0]]*inv[i]%mod *inv[n - a[0] -i]%mod)%mod;

            for(int i=0;i<= a[0] ; i+=2)
                    ansj = (ansj + fact[a[0]]*inv[i]%mod *inv[a[0]-i]%mod)%mod;
            System.out.println(ansj * anso % mod);

        }
        sc.close();
    }
}

End