【排列组合】统计素数和偶数个数

解题思路:

理解题意：给一个数组，例如 int[]arr={1,3,3,3,2,2,4}

下标集合I={0，1，2，3，4，5,6}

R1是I下标集合的一个子集例如{0，1，2，5,6}或者{2，4，5}这样

而R2是R1在I中的补集，也就是I中抛去R1拿走的元素，剩下的元素构成的集合

根据前面的例子R2={3，4}或者{1，3,6}

但是R1和R2还不是随便取的，而是必须保证按照R1和R2俩个下标集合从arr数组中取出的元素之和必须是偶数

按照R1下标取出的元素集合是S1={1，3，3,2,4}和为13非偶数所以R1这个下标组合不可取。

而如果R1={0，1，2，3，4}就是可行的，因为此时S1={1，3，3，3，2}和为12是偶数

且R2={5，6}S2={2,4}和为6也是可行的。所以R1可以那样取。题目的意思就是问R1有多少种取法.

是不是感觉很麻烦？？？我也是！！

我的思路：其实不用管R1集合，就直接看把数组的元素分成两部分，并且每部分的和还得是偶数，到底有多少种分法？

一：如果数组中有奇数且个数为奇数，那么无论怎么分都不可能两部分的和都为偶

二：如果数组中有奇数且个数为偶数个则可以分。因为奇数+奇数一定可以得到一个偶数。如果只有奇数个奇数，那么最后肯定要落单的奇数必须得和偶数加或自己一个呆着，两种情况，和都不可能是偶数。奇数+偶数=奇数

三：分成多少种呢？分别计算出只选奇数的方案和只选偶数的方案和素数偶数都选的方案。最后三种方案的和就是总的方案数。

例如数组中奇数有n1个，偶数有n2个

只选奇数的方案有Cn1^2+Cn1^4+Cn1^6+...=2^(n1-1)-1种

只选偶数的方案有Cn2^0+Cn2^1+Cn2^2+Cn2^3+...+Cn2^Cn2^2=2^n2种

偶数和奇数都选的方案=只选奇数方案数*只选偶数方案数

最后将三种方案加和就是结果，我根据观察又发现只要方案三+只选偶数方案也是对的。

当然大家也可以从反向思考求总的方案数就是2^(n1+n2)减去奇数被分成两部分且每部分的个数都是奇数的方案

因为奇数偶数个但每部分如果只有奇数个也是不可能和为偶的。

注意事项:

计算2^n我一开始用的快速幂，因为看到题目里要取模，数据会很大。

结果快速幂只能计算2^31，再多答案都变0了，然后就改成乘一次取一次模。

参考代码:

import java.io.*;
import java.util.Arrays;

/**
 * @Author:杨雨彤
 * @date:2024/1/26 17:21
 */
public class Main {
    static final  int Mod=1000000007;
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static  PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        String s=br.readLine();
        int test=Integer.parseInt(s);
        while(test-->0) {
            int len = Integer.parseInt(br.readLine());
            int oddcount = 0;//记录奇数个数
            int evencount = 0;//记录偶数个数
            String[] s1 = br.readLine().split(" ");
            for (int i = 0; i < len; i++) {
                int num = Integer.parseInt(s1[i]);
                if (num % 2 == 0) {
                    evencount++;
                } else {
                    oddcount++;
                }
            }
            if (oddcount % 2 != 0) {//奇数的个数为奇，肯定不能分成两部分偶，输出0
                pw.println(0);
                pw.flush();
            } else {
                long methodEven = getPower(2, evencount);//只选偶数，其中包括一个偶数都不选的情况
                long methodOdd = oddcount!=0?getPower(2, oddcount - 1) - 1:0;//只选奇数，虽然奇数个数不为奇，但有可能是0，不要忘记考虑
                long methodEO = ((methodEven % Mod) * (methodOdd % Mod)) % Mod;//偶数和奇数都选的方案数
                long total = (methodEO + methodEven ) % Mod;//总的方案数
                pw.println(total % Mod);
                pw.flush();
            }

        }
        pw.close();
        }
    private static long getPower(int base,int index){
        int res=1;
        while(index>0){
            res=(res*2)%Mod;
            index--;
        }
        return res%Mod;
    }
}