Annettuna on bittijono, jossa on $n$ merkkiä. Joka askeleella saat poistaa kaksi vierekkäistä bittiä, jotka ovat samat. Monellako tavalla voit poistaa kaikki bitit?

Esimerkiksi kun bittijono on $100111$, mahdollisia tapoja on $5$:

• $1\underline{00}111 \rightarrow \underline{11}11 \rightarrow \underline{11} \rightarrow$ (tyhjä)
• $1\underline{00}111 \rightarrow 1\underline{11}1 \rightarrow \underline{11} \rightarrow$ (tyhjä)
• $1\underline{00}111 \rightarrow 11\underline{11} \rightarrow \underline{11} \rightarrow$ (tyhjä)
• $100\underline{11}1 \rightarrow 1\underline{00}1 \rightarrow \underline{11} \rightarrow$ (tyhjä)
• $1001\underline{11} \rightarrow 1\underline{00}1 \rightarrow \underline{11} \rightarrow$ (tyhjä)

Voit olettaa, että $1 \le n \le 30$.

Python

Toteuta tiedostoon biterase.py funktio count, joka kertoo, monellako tapaa voit poistaa kaikki bitit.

def count(s):
    # TODO

if __name__ == "__main__":
    print(count("1100")) # 2
    print(count("1001")) # 1
    print(count("100111")) # 5
    print(count("11001")) # 0
    print(count("1100110011100111")) # 113925

Java

Toteuta tiedostoon BitErase.java metodi count, joka kertoo, monellako tapaa voit poistaa kaikki bitit.

public class BitErase {
    public long count(String s) {
        // TODO
    }

    public static void main(String[] args) {
        BitErase b = new BitErase();
        System.out.println(b.count("1100")); // 2
        System.out.println(b.count("1001")); // 1
        System.out.println(b.count("100111")); // 5
        System.out.println(b.count("11001")); // 0
        System.out.println(b.count("1100110011100111")); // 113925
    }
}