首页 > 其他 > 详细

[uva11174]村民排队 递推+组合数+线性求逆元

时间:2018-09-21 22:20:36      阅读:122      评论:0      收藏:0      [点我收藏+]

 

n(n<=40000)个村民排成一列,每个人不能排在自己父亲的前面,有些人的父亲不一定在。问有多少种方案。

 

 

父子关系组成一个森林,加一个虚拟根rt,转化成一棵树。

假设f[i]表示以i为根的子树的排列方案数。

f[i]=f[1]*f[2]*..f[k] /(sum[i]-1)!/sum[1]!*sum[2]!*..sum[k]!)

化简,对每一个i,sum[i]-1在分子出现一次,sum[i]在分母出现一次。

Ans = n!/(sum1*sum2*sum3*...*sumn) 

 

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 const int mod=((int)1e9)+7,maxn=40000,N=40010;
 9 int first[N],sum[N],fa[N];
10 LL jc[N],inv[N];
11 int rt,al;
12 struct node{int x,y,next;}a[N];
13 
14 void ins(int x,int y)
15 {
16     a[++al].x=x;a[al].y=y;
17     a[al].next=first[x];first[x]=al;
18 }
19 
20 void dfs(int x)
21 {
22     sum[x]++;
23     for(int i=first[x];i;i=a[i].next)
24     {
25         dfs(a[i].y);
26         sum[x]+=sum[a[i].y];
27     }
28 }
29 
30 int main()
31 {
32     freopen("a.in","r",stdin);
33     
34     jc[1]=1;
35     for(int i=2;i<=maxn;i++) jc[i]=(jc[i-1]*i)%mod;
36     inv[1]=1;
37     for(int i=2;i<=maxn;i++)
38     {
39         inv[i]=((LL)(mod-mod/i))*inv[mod%i]%mod;
40     }
41     
42     int T,n,m,x,y;
43     scanf("%d",&T);
44     while(T--)
45     {
46         scanf("%d%d",&n,&m);
47         rt=n+1;
48         for(int i=1;i<=n;i++) fa[i]=-1;
49         al=0;
50         memset(first,0,sizeof(first));
51         for(int i=1;i<=m;i++)
52         {
53             scanf("%d%d",&x,&y);
54             fa[x]=y;
55             ins(y,x);
56         }
57         for(int i=1;i<=n;i++)
58             if(fa[i]==-1) fa[i]=rt,ins(rt,i);
59         memset(sum,0,sizeof(sum));
60         dfs(rt);
61         LL ans=jc[sum[rt]-1];
62         for(int i=1;i<=n;i++)
63         {
64             ans=ans*inv[sum[i]]%mod;
65         }
66         printf("%lld\n",ans);
67     }
68     
69     return 0;
70 }

 

 

#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>using namespace std;
typedef long long LL;const int mod=((int)1e9)+7,maxn=40000,N=40010;int first[N],sum[N],fa[N];LL jc[N],inv[N];int rt,al;struct node{int x,y,next;}a[N];
void ins(int x,int y){a[++al].x=x;a[al].y=y;a[al].next=first[x];first[x]=al;}
void dfs(int x){sum[x]++;for(int i=first[x];i;i=a[i].next){dfs(a[i].y);sum[x]+=sum[a[i].y];}}
int main(){freopen("a.in","r",stdin);jc[1]=1;for(int i=2;i<=maxn;i++) jc[i]=(jc[i-1]*i)%mod;inv[1]=1;for(int i=2;i<=maxn;i++){inv[i]=((LL)(mod-mod/i))*inv[mod%i]%mod;}int T,n,m,x,y;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);rt=n+1;for(int i=1;i<=n;i++) fa[i]=-1;al=0;memset(first,0,sizeof(first));for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);fa[x]=y;ins(y,x);}for(int i=1;i<=n;i++)if(fa[i]==-1) fa[i]=rt,ins(rt,i);memset(sum,0,sizeof(sum));dfs(rt);LL ans=jc[sum[rt]-1];for(int i=1;i<=n;i++){ans=ans*inv[sum[i]]%mod;}printf("%lld\n",ans);}return 0;}

[uva11174]村民排队 递推+组合数+线性求逆元

原文:https://www.cnblogs.com/KonjakJuruo/p/9688582.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!