AtCoder Beginner Contest 133 E - Virus Tree 2(组合数学)
2024-08-22 08:21:37
题意
n个点的树k种颜色,距离不超过2的点对需颜色不同,求方案数
Code(copy)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
typedef long long LL;
const int N=100005;
const int MOD=1000000007;
int n,k,jc[N],ny[N],ans,cnt,last[N];
struct edge{int to,next;}e[N*2];
int A(int n,int m)
{
return n<m?0:(LL)jc[n]*ny[n-m]%MOD;
}
void addedge(int u,int v)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void dfs(int x,int fa)
{
int deg=0;
for (int i=last[x];i;i=e[i].next)
{
if (e[i].to==fa) continue;
dfs(e[i].to,x);
deg++;
}
if (!fa) ans=(LL)ans*A(k,deg+1)%MOD;
else ans=(LL)ans*A(k-2,deg)%MOD;
}
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<n;i++)
{
int x,y;scanf("%d%d",&x,&y);
addedge(x,y);
}
jc[0]=jc[1]=ny[0]=ny[1]=1;
for (int i=2;i<=std::max(n,k);i++) jc[i]=(LL)jc[i-1]*i%MOD,ny[i]=(LL)(MOD-MOD/i)*ny[MOD%i]%MOD;
for (int i=2;i<=std::max(n,k);i++) ny[i]=(LL)ny[i-1]*ny[i]%MOD;
ans=1;
dfs(1,0);
printf("%d\n",ans);
return 0;
}
最新文章
- 第三天的学习知识HTML5常用的重要单词
- Android按需添加Google Play服务
- 谢谢博客-园,让我不再有开源AYUI的想法
- 单元测试mock之mockito使用
- lcd 图片
- 使用Visual Studio 2013进行单元测试--初级篇
- 【BZOJ】【3156】防御准备
- 【转】Android屏幕适配全攻略(最权威的官方适配指导)
- C# 采用线程重绘图形要点记录
- phpEXCEL操作全解
- HTML5实战之桌面通知
- ZOJ 1530 - Find The Multiple
- nginx的五种负载算法模式
- loadrunner常用函数总结
- TIOBE:全球编程语言最新排名(Kotlin排名进入前50名)
- tomcat8权限分离
- 「JOISC 2018 Day 3」比太郎的聚会
- SpringBoot系列: Pebble模板引擎语法介绍
- SecureCRT连接linux,Hive中无法使用删除键
- java中元注解有四个
热门文章
- 【洛谷 SP8093】 JZPGYZ - Sevenk Love Oimaster(后缀自动机)
- MySql 严格模式相关配置
- JavaScript HTML DOM元素节点常用操作接口
- Android笔记(七十三) Android权限问题整理 非常全面
- kubernetes-使用Calico配置NetworkPolicy
- 使用Cloudera Manager搭建MapReduce集群及MapReduce HA
- HTML&;CSS基础-外边框
- 自定义jsr-269注解处理器 Error:服务配置文件不正确,或构造处理程序对象javax.annotation.processing.Processor: Provider not found
- DFS遍历拷贝所有子文件夹及目录列表 (Java版)
- SpringBoot -基础学习笔记 - 01