当前位置:网站首页>hdu 4661 Message Passing(木DP&组合数学)
hdu 4661 Message Passing(木DP&组合数学)
2022-07-06 17:56:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
Message Passing
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1187 Accepted Submission(s): 423
Problem Description
There are n people numbered from 1 to n. Each people have a unique message. Some pairs of people can send messages directly to each other, and this relationship forms a structure of a tree. In one turn, exactly one person sends all messages s/he currently has to another person. What is the minimum number of turns needed so that everyone has all the messages? This is not your task. Your task is: count the number of ways that minimizes the number of turns. Two ways are different if there exists some k such that in the k-th turn, the sender or receiver is different in the two ways.
Input
First line, number of test cases, T. Following are T test cases. For each test case, the first line is number of people, n. Following are n-1 lines. Each line contains two numbers.
Sum of all n <= 1000000.
Output
T lines, each line is answer to the corresponding test case. Since the answers may be very large, you should output them modulo 10 9+7.
Sample Input
2
2
1 2
3
1 2
2 3
Sample Output
2
6
Source
zhuyuanchen520 | We have carefully selected several similar problems for you: 501750155013
题意:
n个人,构成树形关系。每一个人有一条独一无二的信息。每一个人能够将自己的信息通过树边。共享给与他相邻的人,共享之后。被共享的人拥有他原有的信息和共享的来的信息。
每次共享为一次操作。问每一个人都拥有全部人的信息最小要的次数的共享方法有多少种。
思路:
easy的出。最短的时间内。当然是每一个节点将自己的信息想外传出去一次。而且接受一次信息,也就是树边的2倍2*(n-1)。 然后能够证明。在最短时间内,全部的传递方式都有一个“信息转换点”——其它节点的信息首先传递到此节点,然后信息再从这个节点向其它节点传递。
事实上我们要求的就是拓扑序有多少种。定义dp[u]表示u节点下面。传到u节点的拓扑序有多少种,cnt[u]表示u有多少个子孙节点,f[i] = i!(i的阶乘)。c[i][j]表示组合数。
如果它有v1,v2,v3个节点。它们的拓扑序分别有dp[v1],dp[v2],dp[v3]这么多种。
那么dp[u] = c[cnt[u]-1][cnt[v1]] * c[cnt[u]-1-cnt[v1]][cnt[v2]] * c[cnt[u]-1-cnt[v1]-cnt[v2]][cnt[v3]] * dp[v1] * dp[v2] * dp[v3](这个自己推推吧)。化简以后。得到dp[u] = f[cnt[u]-1] / ( f[cnt[v1]] * f[cnt[v2]] * f[cnt[v3]] ) * dp[v1] * dp[v2] * dp[v3] 。我们能够在o(n)的时间复杂度内算出以1节点为根的全部dp值(那么以1为根的答案就算出来了)。以及其它一些辅助信息的值。然后按树的结构往下遍历。分别计算以其它节点为根的答案。以上是网上的思路。我想说的是自己的一点理解。为什么知道每一个子树的拓扑序数目。就能够退出自己的拓扑序数目呢。事实上非常好理解的。当每一个子树的拓扑序定下来之后。确定总顺序的时候。
也就是要得到一个长度为cnt[u]拓扑序列。
对于子树i。
也有一个长度为cnt[i]拓扑序列,所以就要在cnt[u]里找cnt[i]个位置。其它子树再在剩下的子树里找。
还有换根的时候该怎么推导。先写出
dp[u]’=dp[u]*(n-sz[v]-1)!*sz[v]!/((n-1)!*dp[v])
dp[v]’=dp[v]*(n-1)!*dp[u]’/((sz[v]-1)!*(n-sz[v])!)。
带入dp[u]’就能够约掉非常多东西了。所以推公式的时候不要急着得到最后答案。还有就是为什么答案数就是拓扑序数的平方。
由于信息传回去的时候就是你拓扑序嘛。和拓扑序数目一样的。
每个正拓扑序能够和一个逆拓扑序组合。所以就有平方种啦。
具体见代码:
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1000010;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
const ll mod=1e9+7;
ll fac[maxn],dp[maxn],ans;
int cnt,sz[maxn],n;
struct node
{
int v;
node *next;
} ed[maxn<<1],*head[maxn];
void adde(int u,int v)
{
ed[cnt].v=v;
ed[cnt].next=head[u];
head[u]=&ed[cnt++];
}
ll pow_mod(ll x,int k)
{
ll base=x,ret=1;
while(k)
{
if(k&1)
ret=(ret*base)%mod;
base=(base*base)%mod;
k>>=1;
}
return ret;
}
ll ni(ll x){ return pow_mod(x,mod-2); }
void dfs(int fa,int u)
{
ll tp;
dp[u]=tp=sz[u]=1;
for(node *p=head[u];p!=NULL;p=p->next)
{
int v=p->v;
if(v==fa)
continue;
dfs(u,v);
tp=(tp*ni(fac[sz[v]]))%mod;
dp[u]=(dp[u]*dp[v])%mod;
sz[u]+=sz[v];
}
dp[u]=(dp[u]*fac[sz[u]-1]%mod*tp)%mod;
}
void solve(int fa,int u,ll tp)
{
ll tt;
ans=(ans+tp*tp%mod)%mod;
for(node *p=head[u];p!=NULL;p=p->next)
{
int v=p->v;
if(v==fa)
continue;
tt=(tp*fac[n-sz[v]-1]%mod*fac[sz[v]])%mod;
tt=(tt*ni(fac[sz[v]-1])%mod*ni(fac[n-sz[v]]))%mod;
solve(u,v,tt);
}
}
int main()
{
int t,i,u,v,rt;
fac[0]=fac[1]=1;
for(i=2;i<maxn;i++)
fac[i]=(i*fac[i-1])%mod;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
cnt=0,ans=0;
for(i=1;i<=n;i++)
head[i]=NULL;
for(i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
adde(u,v);
adde(v,u);
}
rt=(n+1)/2;
dfs(-1,rt);
solve(-1,rt,dp[rt]);
printf("%I64d\n",ans);
}
return 0;
}
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116894.html原文链接:https://javaforall.cn
边栏推荐
- JS reverse -- ob confusion and accelerated music that poked the [hornet's nest]
- golang中的atomic,以及CAS操作
- NEON优化:矩阵转置的指令优化案例
- [advanced C language] 8 written questions of pointer
- Force buckle 1037 Effective boomerang
- LeetCode:1175. Prime permutation
- Metauniverse urban legend 02: metaphor of the number one player
- THREE. AxesHelper is not a constructor
- 云呐|工单管理办法,如何开展工单管理
- 405 method not allowed appears when the third party jumps to the website
猜你喜欢
Yunna | work order management measures, how to carry out work order management
Transplant DAC chip mcp4725 to nuc980
移植DAC芯片MCP4725驱动到NUC980
微信公众号发送模板消息
LeetCode:1175. 质数排列
对C语言数组的再认识
JS reverse -- ob confusion and accelerated music that poked the [hornet's nest]
云呐|工单管理软件,工单管理软件APP
The MySQL database in Alibaba cloud was attacked, and finally the data was found
今日问题-2022/7/4 lambda体中修改String引用类型变量
随机推荐
How to prevent overfitting in cross validation
MySQL script batch queries all tables containing specified field types in the database
字节P7专业级讲解:接口测试常用工具及测试方法,福利文
C语言实例_4
Metauniverse urban legend 02: metaphor of the number one player
Sword finger offer II 035 Minimum time difference - quick sort plus data conversion
Oracle: Practice of CDB restricting PDB resources
golang 基础 —— 数据类型
Clickhouse fields are grouped and aggregated, and SQL is queried according to the granularity of any time period
HMM 笔记
JS reverse -- ob confusion and accelerated music that poked the [hornet's nest]
域分析工具BloodHound的使用说明
[advanced C language] 8 written questions of pointer
C language instance_ five
Go zero micro service practical series (IX. ultimate optimization of seckill performance)
swiper组件中使用video导致全屏错位
数据手册中的词汇
Google released a security update to fix 0 days that have been used in chrome
微信公众号发送模板消息
C语言实例_5