1. 首页
  2. 题解列表
  3. 3171题题解

组合计数+简单归纳

958 阅读 4 评论
原题链接：蓝桥杯2023年第十四届省赛真题-数组分割

解题思路:

很明显实际上就是组合计数,把所有数分成偶数集合和奇数集合


L:表示奇数个数

R:表示偶数个数


当奇数的  个数  为奇数时无解直接输出0即可


只需要枚举s1这个集合的选择，剩下的没有选择的就是s2的元素

偶数集:可以在这个集合里面选择0-R个元素，所有选择方案 sum=C(R,0)+C(R,1)+C(R,2).....+C(R,R)。展开不难发现最终结果就是sum==2^R;


奇数集:只能在这个集合里面选偶数个数也就是0,2,4,6....L      这个也是展开找规律，展开观察可以发现C(L,0)+C(L,2)+C(L,4)....C(L,L)==2^(L-1)


奇数和偶数的所有选择方案就是 2^R * 2^(L-1)对1000000007取余即可,因为次方次数只有1000左右，无论是快速幂还是暴力均可

注意事项: 多展开，多画图，找到规律再做题，不要做一步看一步，这样大概率是做不出来题的。

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int mod=1000000007;
LL qmi(LL a,LL p){
    if(p<0) return 1;
    LL res=1;
    while (p){
        if(p&1) res=res*a%mod;
        a=a*a%mod;
        p>>=1;
    }
    return res%mod;
}
int main(){
   int T;
   cin>>T;
    while (T--){
        LL n;
        cin>>n;
        LL l=0,r=0;//l表示奇数个数,r表示偶数个数
        int x;
        for(int i=1;i<=n;i++){
            cin>>x;
            if(x%2==0) r++;
            else l++;
        }
        if(l&1){
            cout<<0<<endl;
        }else{
            cout<<qmi(2,l-1)%mod*qmi(2,r)%mod<<endl;//也可以直接写成qmi(2,l-1+r)
        }
    }
}
点赞(0)
　

0.0分

10 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
点进来你会后悔的
点进来你会后悔的
简简单单的循环
简简单单的循环
简单的回文数
简单的回文数

评论列表 共有 4 条评论

TOTP 1年前 回复TA 
@油专软工狗 @1583790725 这个代码一坨太抽象了，代码丢了不少。不知道你写的代码是什么。
油专软工狗 1年前 回复TA 
@油专软工狗 为啥不对捏
油专软工狗 1年前 回复TA 
@油专软工狗 //判断奇数( (a&1)==1);判偶( (a&1) ==0)             if((l&1)==1){                 res[i]=0;             }else{                 res[i]= (int) (qmi(2L,l-1)%mod*qmi(2L,r)%mod);                 //也可以直接写成qmi(2,l-1+r)             }         }          for(int i=1;i<=n;i++){             System.out.println(res[i]);         }     }     static Long qmi(long a,long p) {         if(p<0) return 1L;         long res=1L;         while (p!=0){             if((p&1)==1)                 res=res*a%mod;             a=a*a%mod;             p>>=1;         }         return res%mod;     } }
油专软工狗 1年前 回复TA 
import java.util.Scanner;
import java.lang.Math;

public class Main {
    static int mod=1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();

        int res[]=new int[n+1];
        long l=0L,r=0L;//l表示奇数个数,r表示偶数个数
        for(int i=1;i<=n;i++){
            int m=sc.nextInt();

            for(int j=0;j<m;j++){
                int s=sc.nextInt();
                //System.out.println(s);
                if(s%2!=0)
                    l++;
                else
                    r++;
            }
            //判断奇数(