标题马虎:有n个人组成森林关系。现在要把他们排成一列,使外甥不在老爹前面,求方案数。n<=五千0。
标题马虎:有n个人组成森林关系。现在要把她们排成一列,使外孙子不在阿爸前边,求方案数。n<=四千0。
惊叹数学之妙。
惊讶数学之妙。
首先映入眼帘森林,不释迦牟尼佛3个一级点做根。
首先映入眼帘森林,不比来佛1个顶尖点做根。
设f[i]意味着处理完i与i的子树的方案数,size[i]意味着子树大小,j是i的幼子。
设f[i]代表处理完i与i的子树的方案数,size[i]代表子树大小,j是i的外孙子。
首先对此两棵子树,它们之间是互不影响的,所以方案数相应相乘,那有的象征出来就是:
首先对于两棵子树,它们中间是互不影响的,所以方案数相应相乘,这部分代表出来就是:
然后思想对于一种对于每种j的当中顺序已经鲜明,求i有微微种放法?那就也正是2个可重集合的模型(在j内的一定于四个再一次成分):
然后合计对于一种对于每种j的当中顺序已经分明,求i有微微种放法?那就一定于1个可重集合的模型(在j内的一对一于一个重复成分):
然后两有些用乘法原理乘起来,正是f[i]:
然后两片段用乘法原理乘起来,便是f[i]:
那一个就能够写那道题了。
那个就能够写那道题了。
但实质上能够进一步化简?大家来考虑把多个f[j]拆开。设j的外甥是x:
但实在能够进一步化简?我们来考虑把1个f[j]拆开。设j的幼子是x:
然后f[i]的架子里的size[j]!可以被(size[j]-1)!消成size[j]。
然后f[i]的姿态里的size[j]!可以被(size[j]-1)!消成size[j]。
思维发散一下,f[i]内的size!和(size-1)!都会被消成1/size。
思维发散一下,f[i]内的size!和(size-1)!都会被消成1/size。
最终的答案是f[0]:
最终的答案是f[0]:
因为(size[0]-1)!=n!,最终答案便是:
因为(size[0]-1)!=n!,最终答案就是:
#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;
}
#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;
}
Stand in a Line
Stand in a Line