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)
- #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;
- }
- #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(inti=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;
- }
来源: http://www.bubuko.com/infodetail-2776317.html