2024/3/23打卡数组分割（第14届蓝桥杯）—

2024/3/23打卡数组分割（第14届蓝桥杯）——二项式+快速幂

题目

思路

分析该题，要将集合 $A$ 划分成两个子集 $a_i,a_j$ ，且两个子集的和都是偶数。

可知：偶数 + 偶数 = 偶数；偶数 + 奇数 = 奇数；奇数 + 奇数 = 偶数；

分析可得：如果该集合的和为奇数，就不能分成两个和是偶数的子集。否则，可以划分。

因此我们只需要判断集合的和为偶数的所有子集的方案。再根据已知可得，我们只需要保证某个子集，比如 $a_i$ 的和为偶数，则另一个子集之和必然为偶数。

如何计算子集为偶数的所有方案数？

如果我们想要子集的和全是偶数，那我们可以选择：

全是偶数的数来作为子集（剩下的为偶数-偶数=偶数）
或者偶数个奇数来作为子集（偶数个奇数之和=偶数）

最后将二者相乘（相当于全是偶数的各个方案与偶数个奇数的各个方案进行合并，合并后子集的仍然是偶数），就可以得出所有方案。

如何找全是偶数的方案？

我们可以在集合 $A$ 中找到偶数的个数，记为 $r$ ，奇数的个数记为 $l$ 。

那么我们只需要在 $r$ 个偶数中选取全是偶数的方案（剩下的元素和也一定是偶数）。

那么我们可以选取 0 个，1 个，2 个... r 个。

相当于 $C(r,0)+C(r,1)+C(r,2)+....+C(r,r)$

那么就可以使用二项式定理 $(1+1)^r= \sum_{x=0}^{r}C_r^x=C_r^0+C_r^1+C_r^2+...+C_r^r$

因此全是偶数的方案个数为： $2^r$

如何找偶数个奇数的方案？

与找偶数类似

我们选取 0 个，2 个，4 个... 奇数。

相当于 $C(l,0)+C(l,2)+C(l,4)+....$

二项式定理 $(1+1)^l= \sum_{x=0}^{l}C_l^x \ \ \ \ \ \ \ \ \ \ \ \ \ =C_l^0+C_l^1+C_l^2+...+C_l^r$ ①

$(1-1)^l= \sum_{x=0}^{l}C_l^x1^{l-x}(-1)^x=C_l^0-C_l^1+C_l^2-C_l^3$ ②

①和②相加可得 $2^l=2(C_l^0+C_l^2+C_l^4+...)$

那么偶数个奇数的方案个数为 $C_l^0+C_l^2+C_l^4+... =2^{l-1}$

总方案个数为 $2^r*2^{l-1}$

代码

可以使用快速幂思想，计算更快快速幂（求解原理+例题）-CSDN博客

数据范围小我就没用

import java.io.*;

class Main{
    static int N = 1010 , mod = 1000000007;
    static int t;
    static int[] a = new int[N];
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(in.readLine());
        while(t-->0){
            int l=0,r=0; // 分别表示奇数，偶数的个数
            int n = Integer.parseInt(in.readLine());
            String[] s = in.readLine().split(" ");
            for(int i=1;i<=n;i++) {
               a[i] = Integer.parseInt(s[i-1]); 
               if(a[i]%2==0) r++;
               else l++;
            }
            if(l%2!=0){ // 如果有奇数个奇数，说明集合之和为奇数
                System.out.println(0);
                continue;
            } 
            long rs = 1,ls = 1; // 分别计算2^r,2^(l-1)
            for(int i=0;i<r;i++) rs = (rs*2)%mod;
            for(int i=0;i<l-1;i++) ls = (ls*2)%mod;
            System.out.println((rs*ls)%mod);
        }
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/488901.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！