题解：P2624 [HNOI2008] 明明的烦恼

题解：P2624 [HNOI2008] 明明的烦恼

不会 $prufer$ 序列的请右转树的计数，先将 $prufer$ 序列掌握再做这题。

设有 $n$ 个节点，$deg_i$ 为每个节点的度数，由上题可得，此时可能的无根树的方案为：

$$\frac{(n-2)!}{\prod_{i=1}^{n}(deg_i-1)!}$$

但是这题只给了我们部分节点的度数，要怎么办呢？

我们可以先算题目给定度数的节点对方案数的贡献，设 $sum$ 为有度数的节点的 $deg_i-1$ 总和，即为 $\sum_{i=1}^{n}(deg_i-1)$（不包括没有度数限制的节点），$sum$ 就是这些有度数限制的节点在这颗树的 $prufer$ 序列里占的长度，每个节点会在 $prufer$ 序列中出现 $deg_i-1$ 次。

因为一颗有 $n$ 个节点的无根树的 $prufer$ 序列长度为 $n-2$，所以如果 $sum>n-2$ 则答案无解，否则方案数即为：

$$C_{n-2}^{{sum}\times\frac{sum!}{\sum_{i=1}}(deg_i-1)!}$$

可以将 $C_{n-2}^{sum}$ 理解为将 $sum$ 个数放在长度为 $n-2$ 的 $prufer$ 中的方案数。

那么为什么是乘上 $\frac{sum!}{\sum_{i=1}^{n}(deg_i-1)!}$ 而不是 $\frac{(n-2)!}{\sum_{i=1}^{n}(deg_i-1)!}$ 呢？

让我们回忆一下 $prufer$ 序列的计算方法，因为这些数有 $sum$ 个，所以分子为 $sum$ 的全排列数，又因为每个节点会在 $prufer$ 序列中出现 $deg_i-1$ 次，所以要减去每种相同节点的全排列数。

那么剩下的部分怎么办呢？

可以发现剩下的 $prufer$ 序列没填的部分可以任意填没有限制度数的节点，剩下的 $prufer$ 序列没填的部分的长度为 $(n-2)-sum$（因为已经填了 $sum$ 个），设还没有度数限制的节点数为 $cnt$，则这部分的方案数即为 $cnt^{n-2-sum}$。

综上所述，最终答案的方案数即为：

$$C_{n-2}^{{sum}\times\frac{sum!}{\sum_{i=1}}(deg_i-1)!}\times cnt^{n-2-sum}$$

化简后得：

$$\frac{A_{n-2}^{{sum}}{\sum_{i=1}}(deg_i-1)!}\times cnt^{n-2-sum}$$

接下来写个高精度再写个质因数分解就完成了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=1e8;
int n,sum,d[1550],p[1010],pr[1010],pi,phi[1010]; 
void init(){//提前计算每个数的最小质因子 p[1]=1;for(int i=2;i<=1000;i++){if(!p[i]){pr[++pi]=i;phi[i]=i;}for(int j=1;j<=pi&&i*pr[j]<=1000;j++){p[i*pr[j]]=1;phi[i*pr[j]]=pr[j];if(i%pr[j]==0)break;}}
}
ll vis[1010];
struct N{//高精度 ll a[100010],l;N(){memset(a,0,sizeof(a));l=1;}
};
N operator*(N a,ll b){//高精乘 for(int i=1;i<=a.l;i++)a.a[i]*=b;for(int i=1;i<=a.l;i++){a.a[i+1]+=a.a[i]/P;a.a[i]%=P;if(a.l==i&&a.a[i+1])a.l++;}while(a.l>1&&a.a[a.l]==0)a.l--;return a;
}
N operator/(N a,ll b){//高精除 ll now=0;for(int i=a.l;i>=1;i--){now=now*10+a.a[i];a.a[i]=now/b;now%=b;}while(a.a[a.l]==0&&a.l>1)a.l--;return a;
}
void prr(N ans){//输出 cout<<ans.a[ans.l];for(int i=ans.l-1;i>=1;i--){int t=to_string(ans.a[i]).size();while(t<8){cout<<0;t++;}cout<<ans.a[i];}cout<<'\n';
}
void f(int x,int k){//质因数分解 while(x>1){vis[phi[x]]+=k;x/=phi[x];}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);init();cin>>n;for(int i=1;i<=n;i++){cin>>d[i];if(d[i]!=-1)sum+=d[i]-1;}if(n==1){//特判n=1的情况 cout<<(d[1]<1);return 0;}if(sum>(n-2)){//如果sum>n-2则无解 cout<<0;return 0;}int cnt=n;N ans;ans.a[1]=1;ll aa=n-2,bb=sum;for(int i=aa-bb+1;i<=aa;i++){//计算A(n-2,sum) f(i,1);}for(int i=1;i<=n;i++){//计算相同点的全排列数 if(d[i]==-1)continue;cnt--;while(d[i]>1){f(d[i]-1,-1);d[i]--;}}for(int i=1;i<=n-sum-2;i++)f(cnt,1);//计算没有度数限制的点的放置方案数 for(int j=pi;j>=1;j--){//累计答案 while(vis[pr[j]]>0)ans=ans*pr[j],vis[pr[j]]--;}for(int j=pi;j>=1;j--){while(vis[pr[j]]>0)ans=ans/pr[j],vis[pr[j]]--;}prr(ans);return 0;
}