开发网站开始的工作,网站被抓取,东莞保安公司排名,免费稳定的云服务器正题
题目大意:https://www.luogu.org/problem/P2290 题目大意
一棵树无根树第iii个点的度数为did_idi#xff0c;求树的数量。 解题思路
更具pruferpruferprufer序列的推论我们可以知道答案就是(n−2)!∏i1n(di−1)!\frac{(n-2)!}{\prod_{i1}^n(d_i-1)!}∏i1n(di−1…正题
题目大意:https://www.luogu.org/problem/P2290 题目大意
一棵树无根树第iii个点的度数为did_idi求树的数量。 解题思路
更具pruferpruferprufer序列的推论我们可以知道答案就是(n−2)!∏i1n(di−1)!\frac{(n-2)!}{\prod_{i1}^n(d_i-1)!}∏i1n(di−1)!(n−2)!
然后这就是有重复重排的式子所以就是要求n−2n-2n−2个数iii有di−1d_i-1di−1个求排列数。
组合数计算即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N151;
ll n,d[N],c[N][N],ans1,sum;
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,d[i]),sumd[i]-1;if(sum!n-2){printf(0);return 0;}c[0][0]1;for(ll i0;in;i)for(ll j1;ji;j)c[i][j]c[i-1][j-1]c[i-1][j];sum0;for(ll i1;in;i)ans*c[n-sum-1][d[i]],sumd[i]-1;printf(%lld,ans);
}
