| 等 级 | |
| 排 名 | 15491 |
| 经 验 | 792 |
| 参赛次数 | 0 |
| 文章发表 | 4 |
| 年 龄 | 0 |
| 在职情况 | 学生 |
| 学 校 | |
| 专 业 |
自我简介：
你可能喜欢
2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）浏览：729 |
C语言程序设计教程（第三版）课后习题8.2 （C++代码）浏览：1184 |
C语言程序设计教程（第三版）课后习题6.2 （C++代码）浏览：957 |
字符串的输入输出处理 （C语言代码）浏览：670 |
简单的a+b （C语言代码）浏览：676 |
解题思路:
很明显实际上就是组合计数,把所有数分成偶数集合和奇数集合
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分
17 人评分
评论区
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++;
}
//判断奇数(
2023-04-18 12:07:59
- «
- 1
- »
油专软工狗 2023-04-18 12:08:48 |
//判断奇数( (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; } }
油专软工狗 2023-04-18 12:09:01 |
为啥不对捏
TOTP 2023-04-20 15:08:18 |
@1583790725 这个代码一坨太抽象了，代码丢了不少。不知道你写的代码是什么。