澳门永利备用网址  首先映入眼帘森林,  首先映入眼帘森林

  因为(size[0]-1)!=n!,最后答案就是:

  然后两部分用乘法原理乘起来,就是f[i]:

 

  澳门永利备用网址 1

  感叹数学之妙。

  澳门永利备用网址 2

  这么些就足以写那道题了。

 

  设f[i]意味着处理完i与i的子树的方案数,size[i]代表子树大小,j是i的孙子。

  标题马虎:有n个人组成森林关系。今后要把他们排成一列,使外甥不在老爹前面,求方案数。n<=40000。

  然后f[i]的姿势里的size[j]!可以被(size[j]-1)!消成size[j]。

  澳门永利备用网址 3  

  但实在能够进一步化简?大家来考虑把三个f[j]拆开。设j的幼子是x:

Stand in a Line

  最终的答案是f[0]:

  然后思想对于一种对于每一种j的内部顺序已经规定,求i有稍许种放法?那就一定于一个可重集合的模子(在j内的也等于三个重新成分):

  澳门永利备用网址 4

  首先对于两棵子树,它们之间是互不影响的,所以方案数相应相乘,那部分代表出来正是:

  思维发散一下,f[i]内的size!和(size-1)!都会被消成1/size。

  惊叹数学之妙。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
#define FILE "11174"
using namespace std;

const int N = 40010;
const int Mod = 1000000007;
struct Node{int to,next;}E[N];
int n,m,head[N],tot;
int J[N],Ny[N],size[N],fa[N];

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void link(int u,int v){
  E[++tot]=(Node){v,head[u]};
  head[u]=tot;
}

inline void pre(){
  Ny[1]=J[1]=1;
  for(int i=2;i<N;++i){
    J[i]=1ll*J[i-1]*i%Mod;
    Ny[i]=1ll*(Mod-Mod/i)*Ny[Mod%i]%Mod;
  }
}

inline void dfs(int x){
  size[x]=1;
  for(int e=head[x];e;e=E[e].next)
    dfs(E[e].to),size[x]+=size[E[e].to];
}

inline void solve(int Ans=0){
  memset(fa,0,sizeof(fa));
  memset(head,0,sizeof(head));
  n=gi();m=gi();tot=0;
  for(int i=1;i<=m;++i)fa[gi()]=gi();
  for(int i=1;i<=n;++i)link(fa[i],i);
  dfs(0);Ans=J[n];
  for(int i=1;i<=n;++i)Ans=1ll*Ans*Ny[size[i]]%Mod;
  printf("%d\n",(Ans+Mod)%Mod);
}

int main()
{
  freopen(FILE".in","r",stdin);
  freopen(FILE".out","w",stdout);
  pre();int Case=gi();while(Case--)solve();
  fclose(stdin);fclose(stdout);
  return 0;
}

澳门永利备用网址 5澳门永利备用网址 6

  然后思想对于一种对于每种j的内部顺序已经分明,求i有稍许种放法?那就相当于三个可重集合的模子(在j内的一对一于二个重新成分):

  因为(size[0]-1)!=n!,最后答案正是:

  澳门永利备用网址 7

  澳门永利备用网址 8

  首先对于两棵子树,它们中间是互不影响的,所以方案数相应相乘,那有个别意味出来正是:

  但实质上能够进一步化简?大家来考虑把二个f[j]拆开。设j的孙子是x:

  然后两局地用乘法原理乘起来,正是f[i]:

  澳门永利备用网址 9

澳门永利备用网址 10澳门永利备用网址 11

  思维发散一下,f[i]内的size!和(size-1)!都会被消成1/size。

  标题马虎:有n个人组成森林关系。今后要把他们排成一列,使外孙子不在阿爹面前,求方案数。n<=四千0。

  澳门永利备用网址 12

  首先映入眼帘森林,不释迦牟尼佛三个顶尖点做根。

  设f[i]表示处理完i与i的子树的方案数,size[i]意味着子树大小,j是i的孙子。

  澳门永利备用网址 13

  那些就能够写那道题了。

Stand in a Line

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
#define FILE "11174"
using namespace std;

const int N = 40010;
const int Mod = 1000000007;
struct Node{int to,next;}E[N];
int n,m,head[N],tot;
int J[N],Ny[N],size[N],fa[N];

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void link(int u,int v){
  E[++tot]=(Node){v,head[u]};
  head[u]=tot;
}

inline void pre(){
  Ny[1]=J[1]=1;
  for(int i=2;i<N;++i){
    J[i]=1ll*J[i-1]*i%Mod;
    Ny[i]=1ll*(Mod-Mod/i)*Ny[Mod%i]%Mod;
  }
}

inline void dfs(int x){
  size[x]=1;
  for(int e=head[x];e;e=E[e].next)
    dfs(E[e].to),size[x]+=size[E[e].to];
}

inline void solve(int Ans=0){
  memset(fa,0,sizeof(fa));
  memset(head,0,sizeof(head));
  n=gi();m=gi();tot=0;
  for(int i=1;i<=m;++i)fa[gi()]=gi();
  for(int i=1;i<=n;++i)link(fa[i],i);
  dfs(0);Ans=J[n];
  for(int i=1;i<=n;++i)Ans=1ll*Ans*Ny[size[i]]%Mod;
  printf("%d\n",(Ans+Mod)%Mod);
}

int main()
{
  freopen(FILE".in","r",stdin);
  freopen(FILE".out","w",stdout);
  pre();int Case=gi();while(Case--)solve();
  fclose(stdin);fclose(stdout);
  return 0;
}

  澳门永利备用网址 14

  然后f[i]的姿势里的size[j]!可以被(size[j]-1)!消成size[j]。

  澳门永利备用网址 15

  首先映入眼帘森林,不世尊1个一级点做根。

  澳门永利备用网址 16  

  最终的答案是f[0]: