NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2017高中組決賽
 B. 魔法鏈

作者 主題: B. 魔法鏈  (閱讀 221 次)

oToToT

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
B. 魔法鏈
« 於: 三月 19, 2018, 02:30:02 pm »

代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

const int vn=2000+3;

vector <int> edges[vn];

const lld mod=1e9+7;

#define pr pair<lld,lld>
#define F first
#define S second

lld fp(lld n,lld a){
lld re=1;
for(;a;a/=2){
if(a&1){
re*=n;
re%=mod;
}
n*=n;
n%=mod;
}
return re;
}

lld func(lld n){return fp(n,mod-2);}

lld up[vn],dn[vn];

void init(){
up[1]=1;
dn[1]=1;
for(int i=2;i<vn;i++){
up[i]=up[i-1]*i%mod;
dn[i]=dn[i-1]*func(i)%mod;
}
}

lld C(lld n,lld m){
return ((up[n]*dn[m]%mod)*dn[n-m])%mod;
}

pr dfs(int p,int nw){
lld ans=1;
vector<pr> v;
for(auto au:edges[nw]){
if(au==p) continue;
v.push_back(dfs(nw,au));
}
lld sum=0;
for(auto au:v){sum+=au.S;}
lld ssum=sum;
for(auto au:v){
ans*=au.F;
ans%=mod;
}
for(int i=0;i<(int)v.size()-1;i++){
ans*=C(sum,v[i].S);
ans%=mod;
sum-=v[i].S;
}
return {ans,ssum+1};
}

int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int N;
cin>>N;
init();
int a,b;
while(cin>>a>>b){
a--;
b--;
edges[a].push_back(b);
edges[b].push_back(a);
}
lld ans=0;
for(int i=0;i<N;i++){
ans+=dfs(i,i).F;
ans%=mod;
}
cout<<ans<<endl;
return 0;
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2017高中組決賽
 B. 魔法鏈