排列组合题目

组合数的计算

C(n, 0)+C(n, 1)+...+C(n, n) = 2^n
n是偶数的时候，C(n, 0)+C(n, 2)+...+C(n, n)=2^(n-1)
n是奇数的时候，C(n, 1)+C(n, 3)+...+C(n, n)=2^(n-1)
注意某些组合问题，回溯问题可以直接借用这个方式求解
5.12阿里
小红定义一个数组是好数组，当且仅当所有奇数出现了奇数次，所有偶数出现了偶数次。现在小红拿到了一个数组，她希望取一个该数组的非空子序列(可以不连续)，使得子序列是好数组。你能帮小红求出子序列的方案数吗?由于答案过大，请对1e9+ 7取模。
对于每个数字，如果该数字为奇数，且该数字一共出现了x次，则出现奇数次的方案数为c(x,1)+c(x,3)+c(x,5)+…+c(x,x).其中c表示组合数，这个大小就是2^(x-1)，但是该数字也可以不出现，所以还要加一，一共就是2^(x-1)+1种方案

偶数就是c(x,0)+c(x,2)+…c(x,x),这个也是2^(x-1),然后乘起来，再减去全部都不出现的一次，即减去空串的情况，就是最后答案

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int a[100010],pow2[100100];
map<int,int>mp;
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]++;
    }
    pow2[0]=1;
    int ans=1;
    for(int i=1;i<=n;i++)pow2[i]=pow2[i-1]*2%mod;
    for(auto i:mp){
        if(i.first&1)
        ans=ans*(pow2[i.second-1]+1)%mod;
        else ans=ans*pow2[i.second-1]%mod;
    }
    cout<<ans-1;
}

组合数的计算

5.12阿里