ARC044 B - 最短路問題

B - 最短路問題

概要

長さNの数列Aが与えられる。
A[i]を頂点0から頂点iまでの最短距離とするようなN頂点連結無向グラフは何通りあるか。
（mod 10^9+7して解答）

制約

1 ≦ N ≦ 10^5

方針

まずは不適切なインプットを除外する。不適切なインプットは下記の通り。

• A[0]が0でない
• 0でないiについて、A[i]が0

次に、各頂点を頂点0からの最短距離が同じもの同士でグルーピングしてゆく。
すると、距離iのグループの頂点は、距離i-1・距離i・距離i+1のグループの頂点と隣接することがありえ、
かつそれ以外のグループと隣接することはない。
なお、距離iのグループ個数が0なのに距離i+1のグループ個数が1以上の場合は、不適切なインプットなので除外する。

距離1のグループから順に何通りの辺のつなぎ方があるかを見てゆく。
a[i]：距離iのグループ個数とする。

①距離i-1のグループから距離iのグループに張られる辺の通り数
{(2^(a[i-1])-1)}^a[i]

②距離iのグループ間で張られる辺の通り数
2^(a[i] * (a[i] -1) / 2)

これらを順番にかけ合わせてゆくとよい。

解答

Submission #4725484 - AtCoder Regular Contest 044

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

ll mod(ll a, ll b){
  a %= b;
  return a < 0 ? a + b : a;
}

ll powmod(ll a, ll b){
  if(b == 0) return 1;
  if(b & 1) {
    return a * powmod(a, b - 1) % MOD;
  } else {
    ll d = powmod(a, b / 2) % MOD;
    return d * d % MOD;
  }
}

ll sub(ll a, ll b){
  a %= MOD, b %= MOD;
  a -= b;
  return a < 0 ? a + MOD : a;
}

ll inv(ll a){
	return powmod(a, MOD - 2);
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	ll N;
	cin >> N;

	vector<ll> A(N, 0);
	rep(i, N) cin >> A[i];

	if(A[0] != 0){
		cout << 0 << endl;
		return 0;
	}
	vector<ll> a(N, 0);
	rep(i, N) {
		if(i > 0 && A[i] == 0){
			cout << 0 << endl;
			return 0;
		}
		a[A[i]]++;
	}


	ll dep = 0;
	for(ll i = 1; i < N - 1; i++){
		if(a[i] == 0 && a[i+1] > 0){
			cout << 0 << endl;
			return 0;
		}
		if(a[i] > 0) dep = i;
	}

	ll ans = 1;
	for(ll i = 1; i <= dep; i++){

		ll x = powmod(2LL, a[i-1]);

		ans *= powmod(sub(x, 1), a[i]);
		ans %= MOD;

		ans *= powmod(2LL, a[i] * (a[i] - 1 ) / 2);
		ans %= MOD;
	}

	cout << ans << endl;
}