ARC044-B：最短路問題

数え上げ

問題

https://beta.atcoder.jp/contests/arc044/tasks/arc044_b

N 頂点のグラフが与えられる。頂点 1 から頂点 i への最短路を a_i とするように辺を張るとき、辺の張り方は何通りか求めよ。

考え方

自明なケースを除く。まず 1 から 1 への最短路は 0 であるから、頂点 1 の最短路が 0 以外の場合は 0 通りである。また 1 以外の頂点で最短路が 0 にすることはできないので、1 以外で最短路が 0 となっている頂点が存在する場合は 0 通りである。また、 最短路が連続になっていない頂点が存在する場合、つまり最短路が i と i+2 となっている場合は、最短路が i+2 になるように辺を張ることはできないので 0 通りである。それ以外のケースについて考える。

まず頂点 1 から最短路が 1 となっている頂点には必ず辺を張らないといけない。これは 1 通りで確定する。最短路が同一の頂点に関しては辺を張っても張らなくてもよい。辺の数は同一の最短路の頂点数を k とすると k(k-1)/2 である。それぞれの辺について、張る・張らないという2通りの辺の張り方が考えられるため、辺の張り方は 2k(k-1)/2 通り存在する。

次に辺の最短路が i-1 と i の頂点の辺の張り方について考える。最短路が i の頂点から i-1 への頂点には少なくとも 1 本は辺を張らないといけない。逆に言うと辺を 1 本以上張ることができる。この時の辺の張り方は最短路が i-1 の頂点の数を l とすると、 2l - 1 通り存在する。最短路が i の頂点数が m あるとき、それぞれについて 2l - 1 通り存在するので全体としては (2l - 1)m 通りとなる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            Map<Long, Long> map = new TreeMap<>();
            int n = in.nextInt();
            long[] a = in.nextLongArray(n);
            if (a[0] != 0) {
                out.println(0);
                return;
            }
            for (int i = 1; i < n; i++) {
                if (a[i] == 0) {
                    out.println(0);
                    return;
                }
            }

            for (long l : a) {
                map.merge(l, 1L, Long::sum);
            }

            long ans = 1;
            if (map.containsKey(1L)) {
                long nc = map.get(1L);
                ans = ans % MOD * power(2, nc*(nc-1)/2, MOD);
            }
            for (long i = 2; i < n; i++) {
                long nc = map.containsKey(i) ? map.get(i) : 0;
                long pc = map.containsKey(i-1) ? map.get(i-1) : 0;

                ans = ans % MOD * power((power(2, pc, MOD) - 1), nc, MOD);
                ans = ans % MOD * power(2, nc*(nc-1)/2, MOD);
            }
            out.println(ans % MOD);

        }

        static long power(long a, long e, long modP) {
            long ret = 1;
            for (; e > 0; e /= 2) {
                if (e % 2 != 0) {
                    ret = (ret * a) % modP;
                }
                a = (a * a) % modP;
            }
            return ret;
        }

ポイント

  • 数え上げはもれなく
  • 二分累乗

類題