专栏文章

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

ssunkuangzheng
P13020题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mip0k5ng
此快照首次捕获于
2025/12/03 04:11
3 个月前
此快照最后确认于
2025/12/03 04:11
3 个月前
查看原文
以 rr 为根的答案是 ∏i=1n(degi−[i≠r])!\prod \limits_{i=1}^n (\text{deg}_i - [i \ne r])!，求和化简后即为 ∑degi⋅∏i=1n(degi−1)!=(2n−2)∏i=1n(degi−1)!\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=1n=1 时答案是 11。
CPP
#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);
}
然而注意到模数是 29×592^9\times 5^9，因此只要有一个度数大于等于 4141 的点答案就一定是 00。这就意味着本质不同的根 rr 只有 4040 个，对每一个分别暴力计算一次 ∏i=1n(degi−[i≠r])!\prod \limits_{i=1}^n (\text{deg}_i - [i \ne r])! 也可通过。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...