题解：P13020 [GESP202506 八级] 遍历计数

· · 题解

以 r 为根的答案是 \prod \limits_{i=1}^n (\text{deg}_i - [i \ne r])!，求和化简后即为 \sum \text{deg}_i \cdot \prod\limits_{i=1}^n (\text{deg}_i - 1)! = (2n-2)\prod\limits_{i=1}^n(\text{deg}_i -1)!。注意 n=1 时答案是 1。

#import<iostream>
long d['六'],u,v,n,x=1,P=1e9,i=1;
int main(){
    for(std::cin>>n;i<n;i++)std::cin>>u>>v,d[u]++,d[v]++;
    for(;i;i--)while(--d[i]>0)x=d[i]*x%P;
    std::cout<<(n^1?(2*n-2)*x%P:1);
}

然而注意到模数是 2^9\times 5^9，因此只要有一个度数大于等于 41 的点答案就一定是 0。这就意味着本质不同的根 r 只有 40 个，对每一个分别暴力计算一次 \prod \limits_{i=1}^n (\text{deg}_i - [i \ne r])! 也可通过。