Similar Arrays [CODE FESTIVAL 2017 予選C - B]

atcoder.jp

①長さnの整数列A [A1,A2,A3......An] が与えられる。
②整数列Aの各項に [-1,0,1] から1つ選んで加算していき、整数列Bを作る。
③全ての項の積が偶数となるような整数列Bの作り方は、何通りあるか？

全ての項の積が偶数となるような整数列Bとは、少なくとも1つの項が偶数であるような整数列です。これをもとに、少なくとも1つの項が偶数であるようなパターンを数え上げていきたいところですが、解説にもあるように、この方法で解答を求めるのは難しいようです。

そこで、「少なくとも1つの項が偶数であるような整数列B」ではなく、その逆の「全ての項が奇数であるような整数列B」を考えて、その総数を「整数列Bの作り方の総数」から引くという方法をとります。確率でいうところの余事象の考え方でしょうか。

まず、整数列Bの作り方の総数を考えます。操作候補が3通りあり、それをn個の項に対しておこなうので、総数は3^nです。次に、全ての項が奇数であるような整数列Bの総数を考えます。整数列Aのある項Aiを操作して奇数にできるパターンは、Aiが偶数であれば2通り、Aiが奇数であれば1通りになるので、整数列Aにおける偶数の項の個数をeとしたとき、2^eで求まります。最後に、3^nから2^eを引くことで答えが求まります。

//codefestival2017-qualc-b

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {

		int n = sc.nextInt();
		int e = 0;
		for (int i=0; i<n; i++) {
			if (sc.nextInt()%2 == 0) e++;
		}

		System.out.println((int)(Math.pow(3,n)-Math.pow(2,e)));

	}
}