結果

問題 No.827 総神童数
ユーザー coco18000
提出日時 2019-05-03 23:18:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,519 bytes
コンパイル時間 2,188 ms
コンパイル使用メモリ 177,416 KB
実行使用メモリ 33,684 KB
最終ジャッジ日時 2024-12-31 19:12:10
合計ジャッジ時間 84,989 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 TLE * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

struct Combination
{
    void init(ll n)
    {
        mNumTbl.resize(n + 1);
        mInverseNumTbl.resize(n + 1);
        mNumTbl[0] = 1;
        mInverseNumTbl[0] = 1;
        FOR(i, n + 1, 1)
        {
            mNumTbl[i] = (mNumTbl[i - 1] * i) % MOD;
        }
        FOR(i, n + 1, 1)
        {
            mInverseNumTbl[i] = modpow(mNumTbl[i]);
        }
    }

    ll get(ll n, ll r)
    {
        if (n < r || n < 0)
            return 0;
        return (((mNumTbl[n] * mInverseNumTbl[r]) % MOD) * mInverseNumTbl[n - r]) % MOD;
    }

    //! バイナリ方で累乗を計算
    ll modpow(ll n)
    {
        ll s = 1, p = n;
        for (ll i = 0; (1 << i) <= MOD - 2; ++i, p = (p * p) % MOD)
        {
            if (((MOD - 2) & (1 << i)) == 0)
                continue;
            s *= p;
            s %= MOD;
        }
        return s;
    }

    vector<ll> mInverseNumTbl;
    vector<ll> mNumTbl;
};

struct Vertex
{
    vector<int> n;
    ll depth = INF;
};

Vertex V[200005];
ll dp[200005];
ll N;
Combination cmb;

ll get(int n)
{
    int d = V[n].depth;
    ll c = 0;
    FOR(i, N + 1, 1)
    {
        c += cmb.get(i - 1, d);
        c %= MOD;
    }
    return (((dp[d] * c) % MOD) * dp[N - 1 - d]) % MOD;
}

int main()
{
    cin >> N;
    REP(i, N - 1)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        V[a].n.push_back(b);
        V[b].n.push_back(a);
    }

    queue<pll> q;
    q.push(pll(0, 0));
    while (!q.empty())
    {
        pll t = q.front();
        q.pop();
        V[t.first].depth = t.second;
        int nd = t.second + 1;
        REP(i, V[t.first].n.size())
        {
            int n = V[t.first].n[i];
            if (nd >= V[n].depth)
                continue;
            q.push(pll(n, nd));
        }
    }
    ll t = 1;
    memset(dp, 0, sizeof(dp));
    cmb.init(N + 1);
    FOR(i, N + 1, 1)
    {
        t = (t * i) % MOD;
        dp[i] = t;
    }
    dp[0] = 1;

    // for (int i = N - 1; i >= 0; --i)
    // {
    //     dp[i] += dp[i + 1];
    //     dp[i] %= MOD;
    // }
    // dp[0] = (t * N) % MOD;
    ll ans = 0;
    REP(i, N)
    {
        ans += get(i); //dp[V[i].depth];
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}
0