atcoder 対策 (rate 0~ 1200)

テクニック集

パスカルの三角形

・使い道
組み合わせの数を計算したい時、普通にやろうと考えると分母と分子についてそれぞれfor文で求めることを考えるが、そうすると簡単に桁溢れしてしまう。そこで、このパスカルの三角形を使う。これは二項展開を用いて、組み合わせの数を求めていくもので、dpで実装できる。実装例は下の通り

long[][] pdp = new long[51][51];
        pdp[0][0] = 1;
        for (int x = 1; x <= 50; x++) {             //組み合わせの数の計算
            for (int k = 0; k <= x; k++) {
                if (k - 1 >= 0) {
                    pdp[x][k] = pdp[x-1][k-1] + pdp[x-1][k];
                } else {
                    pdp[x][k] = pdp[x-1][k];
                }
            }
        }