AcWing 5398. 组合数+乘法原理秒了
原题链接
简单
作者:
春江花月夜ovo
,
2024-04-02 23:34:44
,
所有人可见
,
阅读 93
/* /\_/\
* (= ._.)
* / > \>
*/
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
//sum = 奇数, 肯定为0
//sum = 偶数,
const ll mod = 1000000007;
const int N = 1010;
ll C[N][N];
void Init()
{
for (int i = 0; i < N; i ++) C[i][0] = 1, C[i][i] = 1;
for (int i = 1; i < N; i ++)
{
for (int j = 1; j < i; j ++)
{
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
}
void solve()
{
int n;
cin >> n;
ll sum = 0;
ll ji = 0, ou = 0;
for (int i = 1; i <= n; i ++)
{
ll x;
cin >> x;
sum += x;
if (x % 2 == 1) ji ++;
else ou ++;
}
if (sum % 2 == 1) cout << 0 << "\n";
else
{
ll ans = 1;
for (int k = 1; k <= n; k ++)
{
for (int i = 0; i <= ou && i <= k; i ++) //选择偶数的个数
{
int j = k - i; //奇数的个数
if ((j <= ji) && (j % 2 == 0)) ans = (ans + C[ou][i] * C[ji][j]) % mod;
}
}
cout << ans << "\n";
}
}
//全选偶数
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
Init();
int t;
cin >> t;
while (t --) solve();
return 0;
}