ARC 044 B

解いたもののここに載せてないぶんがたまってきました。
今回はこの問題。

arc044.contest.atcoder.jp

頂点数n個のグラフがあります。それぞれ1~nまで番号が振られており、頂点1からの距離が与えられます。
条件を満たすようなグラフは何通りあるでしょうか、という問題です。

回答はこちら。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    long long int pow2result[41];
    // pow2result[i] : (2^(2^i)) % mod
     
    void getpow2result()
    {
        pow2result[0] = 2;
        for(int j = 1; j <= 40; j++){
            pow2result[j] = (pow2result[j - 1] * pow2result[j - 1]) % mod;
        }
        return;
    }
     
    long long int getpow(long long int a, long long int b)
    {
        // a^b % mod を求める
        long long int ans = 1;
        if(a == 0){
            ans = 0;
        } else if(a == 1){
            ans = 1;
        } else if(a == 2){
            for(int i = 40; i >= 0; i--){
                if(b >= (long long int)pow(2, i)){
                    ans = (ans * pow2result[i]) % mod;
                    b -= (long long int)pow(2, i);
                }
            }
        } else {
            long long int result[41];
            result[0] = a;
            for(int j = 1; j <= 40; j++){
                result[j] = (result[j - 1] * result[j - 1]) % mod;
            }
            for(int i = 40; i >= 0; i--){
                if(b >= (long long int)pow(2, i)){
                    ans = (ans * result[i]) % mod;
                    b -= (long long int)pow(2, i);
                }
            }
        }
        return ans;
    }
     
    int main()
    {
        long long int n;
        long long int a[100001] = {};
        long long int ans = 1;
        cin >> n;
        for(int i = 0; i < n; i++){
            int tmp;
            cin >> tmp;
            if(i == 0 && tmp != 0) ans = 0;
            a[tmp]++;
        }
        if(a[0] != 1) ans = 0;
        getpow2result();
        for(int i = 1; i <= n - 1; i++){
            // 頂点1から距離iのノードについて考える
            if(a[i] == 0) continue;
            // if(a[i - 1] == 0 && a[i] > 0){
            //     ans = 0;
            //     break;
            // }
            long long int tmp = (getpow(getpow(2, a[i - 1]) - 1, a[i]) * getpow(2, (a[i] * (a[i] - 1)) / 2)) % mod;
            ans = (ans * tmp) % mod;
        }
        cout << ans << endl;
        return 0;
    }

a[i]は頂点1からの距離がiになる頂点数を表します。頂点1の距離は0になるはずなので、そうでない場合はansの値を0にしておきます。また頂点1からの距離が0になるのは頂点1ただ一つのはずなので、そうでない場合ansの値を0にしておきます。このあとansは乗算することで更新されていくので、このとき最終的な答えも0となり正しくなります。
次に頂点1からの距離が1, 2, 3, ...の順に考えていきます。条件を満たすためには、頂点1からの距離がi-1の頂点のうちの少なくとも一つ以上の頂点との間に辺があることが必要です。距離がi-1の頂点はa[i-1]個あります。これらのうちそれぞれ辺がある/ないの2通りがあるので、2^(a[i-1]) - 1通りあります。1除いているのは、すべての頂点の間に辺がないという場合を除くためです。距離がiとなる頂点はa[i]個ありこれをそれぞれに対して考えないといけないので、a[i]乗します。また、同じ距離になるような頂点の間には辺があっても大丈夫です。辺の取り方はa[i]個から2つえらぶ方法の数と一致します。2つの頂点は繋がっている/いないの2通りあるので全部で2^(a[i] * (a[i]-1))となります。先ほどとは異なり、すべての辺がなくても構わないので1引いたりしません。
これを繰り返せば答えを求められます。2のなんたら乗は何度も何度も使うので先に求めておきます。pow2result[i] : (2^(2^i)) % mod　となっていますが、これは2のなんたら乗の「なんたら」が非常に大きな値になる可能性があるからです。たとえば2^(156)は2^(2^7) * 2^(2^4) * 2^(2^3) * 2^(2^2)に変換して計算するって感じです。底が2以外の時はその都度求めるようにします。

この問題について、2のなんたら乗のみ先に求めるようにしていますが、もともとは
long long int powresult[100010][41] = {};
// powresult[i][j] : i^(2^j) % mod
という配列を求めて必要そうなものを先に求めていました。こうするとREになりました。
このブログを書いてる途中に気づいたんですけど、max100010じゃ全然範囲が足りませんでしたね。
無駄にREやらWAやら重ねてしまった。