蓝桥杯2023年第十四届省赛真题-数组分割（组合数求解，C++版本)

解题思路:
            题目的含义就是将一个数列拆分成两个偶数的子列，考虑以下情况。

            统计奇数和偶数的个数，如果奇数的个数为奇数个，说明整个数列的和是奇数，不可能能拆分成两个偶数的子列，因此这种情况下数量应该是0。

            当奇数个数为偶数时说明可以拆分成两个和为偶数的子列，拆分方式如下。

            首先偶数可以取任意个数，因为偶数任意个数任然是偶数，对于奇数必须取偶数个才能保证剩下的是偶数个并且本身也是偶数。例如一共有m个偶数和n个奇数，那么选取t个偶数和2k个偶数即可构成两个偶数子列。这种情况下为C[m][t]*C[n][2k]，将所有情况相加则有

注意事项:使用longlong类型，不然数据会爆

参考代码:

#include<iostream>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
long long f[1010][1010];
void init(){
	f[0][0] = 1;
	f[1][1] = 1;
	f[1][0] = 1;
	for(int i=2;i<=1000;i++){
		for(int j=0;j<=i;j++){
			if(j==0||j==i){
				f[i][j] = 1;
				continue ;
			}
			f[i][j] = f[i-1][j-1] + f[i-1][j];
			f[i][j]= f[i][j]%mod;
		}
	}
}
int main(){
	init();
	int t;
	cin>>t; 
	while(t--){
		ll count = 0;
		int ji=0,ou=0;
		int n;
		cin>>n;
		for(int i=1;i<=n;i++){
			int temp;
			cin>>temp;
			(temp%2==0)?ou++:ji++;
		}
		if(ji%2==1){
			cout<<0<<endl;
			continue;
		}
		ll jisum = 0;
		for(int i=0;i<=ji;i+=2){
			jisum += f[ji][i];
			jisum%=mod;
		}
		for(int i=0;i<=ou;i++){
			count += f[ou][i]*jisum;
			count%=mod;
		}
		cout<<count<<endl;
	}

	return 0;
}