首页 > 代码库 > 【递推】【推导】【乘法逆元】UVA - 11174 - Stand in a Line
【递推】【推导】【乘法逆元】UVA - 11174 - Stand in a Line
http://blog.csdn.net/u011915301/article/details/43883039
依旧是《训练指南》上的一道例题。书上讲的比较抽象，下面就把解法具体一下。因为涉及到父子关系，因此自然而然可以将n个节点构造成一棵树，最后将形成一个森林。接下来将使用递归的手法。设f(i)是以节点i为树根的子树，节点i有儿子c1,c2,c3....cj共j棵子树。s[i]为树根为i的子树包含的节点数。如果分别先给各个子树内部排序，那么毫无疑问，
共有f(c1)*f(c2)*f(c3)....*f(cj)种情况。接下来又要将所有子树的节点排成一个序列。那么我们事先不考虑各个子树的内部排序，共有(s[i]-1)!/(s[c1]!*s[c2]!*.....s[cj]!种情况。最后，我们将两种情况合起来，就是f(i)的解了，为f(c1)*f(c2)....*f(cj)*(s[i]-1)!/(s[c1]!*s[c2]!*.....s[cj]!)中情况。
事实上，接下来还可以进一步化简，设c1有孩子节点x1,x2,x3....xk。那么f(c1)=f(x1)*f(x2).....f(xk)*(s[c1]-1)!/(s[x1]!*x[x2]!....*x[xk]!)。将f(c1)代入，分子中的(s[c1]-1)!和分母中的s[c1]!约分的s[c1]，然后依次类推，最后分母必然会化为s[1]*s[2]*s[3]...s[n]。因为总共n个节点构成一个森林，因此s[root](root可能为虚拟树根)为n+1,那么最后分母为n!。最后，求出n!/(s[1]*s[2]...s[n])就是我们要求的解。
还要注意的是，最后模运算的时候，1的逆为1。
还有一种理解就是C(11,3)*C(8,6)*5*4*1……就是第一颗子树的结点在11个位子里面选三个，第二颗子树的结点在剩下的8个位子里选6个……然后再乘上每颗子树内部的顺序。
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define MOD 1000000007ll
ll Quick_Pow(ll a,ll p)
{
if(!p) return 1;
ll ans=Quick_Pow(a,p>>1);
ans=ans*ans%MOD;
if((p&1)==1) ans=(a%MOD*ans)%MOD;
return ans;
}
int e,first[40010],__next[40010],v[40010];
void AddEdge(int U,int V){
v[++e]=V;
__next[e]=first[U];
first[U]=e;
}
int T,n,m,fa[40010];
int siz[40010];
void dfs(int U){
siz[U]=1;
for(int i=first[U];i;i=__next[i]){
dfs(v[i]);
siz[U]+=siz[v[i]];
}
}
int main(){
// freopen("uva11174.in","r",stdin);
int x,y;
scanf("%d",&T);
for(;T;--T){
memset(fa,0,sizeof(fa));
memset(first,0,sizeof(first));
e=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
AddEdge(y,x);
fa[x]=y;
}
for(int i=1;i<=n;++i){
if(!fa[i]){
AddEdge(n+1,i);
}
}
dfs(n+1);
ll t=1;
for(int i=1;i<=n;++i){
t=(t*(ll)siz[i])%MOD;
}
ll t2=1;
for(int i=1;i<=n;++i){
t2=(t2*(ll)i)%MOD;
}
printf("%d\n",(int)((t2*Quick_Pow(t,MOD-2))%MOD));
}
return 0;
}
【递推】【推导】【乘法逆元】UVA - 11174 - Stand in a Line