ARC044 B問題 最短路問題

うーむ
くだらないミスを2つしていて随分と時間がかかってしまった…

解き方は簡単で、グラフと言えども、距離順に上から決めてしまえばよい。
同じ距離の頂点に関しては結んでも結ばなくてもよい。(ここの式が少し間違ってて悩んだ)
あと、無意味にmapを使ったせいでこれまた悩んだので反省。死にたい。

ll mod = (ll)1e9+7;

ll ruijo(ll x, ll n, ll mod){
    ll res = 1;
    while(n > 0){
        if(n&1) res = res *x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

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

    ll N; cin >> N;
    ll dist[N]; rep(i, N) cin >> dist[i];
    map<ll, ll> mp;
    rep(i, N) mp[dist[i]]++;
    ll cnt = 0;
    if(dist[0] != 0){
        cout << 0 << endl;
        return 0;
    }
    for(auto it=mp.begin(); it!=mp.end(); it++){
        if(it->first == 0 && it->second > 1){
            cout << 0 << endl;
            return 0;
        }
        if(it->first == cnt){
            cnt++;
        }else{
            cout << 0 << endl;
            return 0;
        }
    }
    ll res = 1;
    for(auto it=mp.begin(); it!=mp.end(); it++){
        auto it2 = it; advance(it2, 1);
        if(it2 == mp.end()){
            break;
        }else{
            res = (res * ruijo(2, (it2->second-1)*it2->second/2, mod))%mod;
            res = (res * ruijo(ruijo(2, it->second, mod)-1, it2->second, mod)) % mod;
        }
    }
    cout << res << endl;
    return 0;
}