結果

問題 No.827 総神童数
ユーザー satou_a_mansatou_a_man
提出日時 2019-05-03 23:18:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,636 bytes
コンパイル時間 2,272 ms
コンパイル使用メモリ 208,764 KB
実行使用メモリ 42,720 KB
最終ジャッジ日時 2023-08-30 06:40:36
合計ジャッジ時間 9,269 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 269 ms
26,344 KB
testcase_01 AC 267 ms
26,448 KB
testcase_02 AC 266 ms
26,432 KB
testcase_03 AC 267 ms
26,284 KB
testcase_04 AC 267 ms
26,344 KB
testcase_05 AC 267 ms
26,468 KB
testcase_06 AC 267 ms
26,576 KB
testcase_07 AC 268 ms
26,440 KB
testcase_08 AC 269 ms
26,292 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
権限があれば一括ダウンロードができます

ソースコード

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