結果

問題 No.827 総神童数
ユーザー satou_a_man
提出日時 2019-05-03 23:18:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,636 bytes
コンパイル時間 1,958 ms
コンパイル使用メモリ 204,372 KB
最終ジャッジ日時 2025-01-07 03:34:33
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

const int p = 1e9+7;

void calc_d(vector<int>& ds, vector<vector<int>>& g, int n) {
  ds[1]=0;
  queue<int> q;
  q.push(1);
  while(!q.empty()) {
    int v=q.front();
    q.pop();
    for(auto& u : g[v]) {
      if(ds[u]==-1) {
	ds[u]=ds[v]+1;
	q.push(u);
      }
    }
  }
}

ll modpow(ll b, ll e) {
  if(e==0)
    return 1LL;
  if(e%2==0) {
    ll t = modpow(b,e/2);
    return (t*t)%p;
  }
  return (b*modpow(b,e-1))%p;
}

vector<ll> fact(1000000);
vector<ll> fact_inv(1000000);

void precalc() {
  fact[0]=1;
  fact_inv[0]=1;
  for(ll i=1; i<=1000000; i++) {
    fact[i]=(fact[i-1]*i)%p;
    fact_inv[i]=modpow(fact[i],p-2);
  }
}

ll nPk(ll n, ll k) {
  return (fact[n]*fact_inv[n-k])%p;
}


vector<ll> f_memo(1000000,-1);
ll f(int d,int n) {
  if(f_memo[d]!=-1)
    return f_memo[d];
  f_memo[d]=0;
  for(int x=d+1;x<=n; x++) {
    f_memo[d]+=(nPk(x-1,d)*fact[n-d-1])%p;
    f_memo[d]%=p;
  }
  return f_memo[d];
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  int n;
  precalc();
  cin>>n;
  vector<vector<int>> g(n+1);
  rep(t,n-1) {
    int u,v;
    cin>>u>>v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> ds(n+1,-1);
  calc_d(ds,g,n);
  ll ans=0;
  for(int i=1; i<=n; i++) {
    //    cout << "f("<<ds[i]<<","<<n<<")="<<f(ds[i],n)<<endl;
    ans+=f(ds[i],n);
    ans%=p;
  }
  cout << ans << endl;
  return 0;
}
0