Biscuits [AtCoder Grand Contest 017 A]

http://agc017.contest.atcoder.jp/tasks/agc017_a

前提知識

• 組合せ数学の知識と実装

解説

http://agc017.contest.atcoder.jp/submissions/1413384

奇数の数の個数をodd,偶数の数の個数をevenとする。
組合せのaCbをC(a,b)と表記する。

P=0の時
答えは2^even * (C(odd,0) + C(odd,2) + C(odd,4) + ...)である。
偶数の取る取らないは問題ではなく、奇数を偶数個取れば全体としてP=0となる。

P=1の時
答えは2^even * (C(odd,1) + C(odd,3) + C(odd,5) + ...)である。
これも偶数の取る取らないは問題ではなく、奇数を奇数個取れば全体としてP=1である。

あとは、組合せを高速に取る方法だが、パスカルの三角形を使うとよい。
組合せを取る方法はいくつかあるが、階乗でやると今回の制約だと途中計算でオーバーフローするかもしれない。
（本番では焦って素因数分解を使って階乗計算をゴリ推したが 罪なコード）
（下のコードではメモ化もしているが、特に無くても間に合う）

typedef long long ll;
#define CMAX 1010
int noinit = 1;ll memo[CMAX][CMAX];
ll aCb(ll a, ll b) {
    if (noinit) {
        rep(i, 0, CMAX) rep(j, 0, CMAX) memo[i][j] = -1;
        noinit = 0;
    }
    if (b == 0 || a == b) return 1;
    if (0 <= memo[a][b]) return memo[a][b];
    return memo[a][b] = aCb(a - 1, b - 1) + aCb(a - 1, b);
}
 
 
int N, P, A[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> P;
    rep(i, 0, N) cin >> A[i];
 
    int odd = 0, even = 0;
    rep(i, 0, N) {
        if (A[i] % 2 == 1) odd++;
        else even++;
    }
 
    ll ans = 0;
    int c = P;
    while (c <= odd) ans += aCb(odd, c), c += 2;
    rep(i, 0, even) ans *= 2;
    printf("%lld\n", ans);
}