B - 最短路問題 AtCoder Regular Contest 044

B - 最短路問題

問題概略
頂点1とiの距離がAiになるようなグラフの総数を数えよ。

制約
10^5

解法
全体を一気に考えると難しくなってしまう。例えば上を満たすような最小限のグラフを全通り作ってやり、そこに辺をどれだけ追加できるかのように考えると駄目。元の形が別でも、辺を追加すると同じにグラフになって被ってしまうことがあるし、なにより単純化されていないから。

今回この問題は小さな複数の問題として分割してやるとうまくいく。
そもそもよくよく考えてみれば頂点が10^5個ある時点で、なにかしら一個一個に対して数を求めていくことを連想するべきだった。

頂点を貼れる条件を考えてみると、距離が2以上離れているものを貼ると最短距離が更新されてしまうため駄目だが、それ意外の0,1は貼れることに気づく。
sを距離i　tを距離i-1　の総数とする
差が0の時は自由に貼れる（1つも貼らなくてもよい）ので、2^(s (s-1))通りになる。（2を辺の数乗している。）
差が1の時は自分より距離が1短いものに対して、すべての頂点sからあるtへ最低1本は辺を貼れば後は自由。
よって(2 ^ t -1 ) ^s （あるsからtに辺を貼る方法が2^t通り、一本も貼らないという状況を除いて-1）
こう数えれば重複はなく、全てかけてやれば良い

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        A = nia(N);
        int[] B = couArray(A);
        if (A[0] != 0 || B[0] > 1) {
            System.out.println("0");
            return;
        }
        long res = 1;
        //階段になっていないと答えが0になる
        for (int i = 1; i < B.length; i++) {
            int s = B[i];
            int t = B[i - 1];
            long same = mPow(2, s * (s - 1L) / 2);
            long one = mPow(mPow(2, t) - 1, s);
            res = mMul(res, same);
            res = mMul(res, one);
        }
        System.out.println(res);
    }