UVa 11174 Stand in a Line

本文主要是介绍UVa 11174 Stand in a Line，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

      依旧是《训练指南》上的一道例题。书上讲的比较抽象，下面就把解法具体一下。因为涉及到父子关系，因此自然而然可以将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。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define MAX 40000+5
#define MOD 1000000007
#define LL long long
using namespace std;LL fac[MAX],N[MAX];//fac[i]为i!,N[i]为i关于MOD的逆
int T,n,m;
int s[MAX],vis[MAX];
vector<int> Tree[MAX];LL inv(LL a,LL n);
void gcd(LL a,LL b,LL& d,LL& x,LL& y);
int dfs(int);int main()
{freopen("data.txt","r",stdin);fac[0]=fac[1]=N[1]=1;//注意1的逆为1for(LL i=2;i<MAX;++i){fac[i]=(i*fac[i-1])%MOD;N[i]=inv(i,MOD);}cin>>T;while(T--){cin>>n>>m;memset(vis,0,sizeof(vis));for(int i=1;i<=n;++i) Tree[i].clear();for(int i=0;i<m;++i){int a,b;cin>>a>>b;Tree[b].push_back(a);}for(int i=1;i<=n;++i){//DFS统计每棵子树包含的节点数if(!vis[i]) dfs(i);}LL ans=fac[n];for(int i=1;i<=n;++i){ans=(ans*N[s[i]])%MOD;}cout<<ans<<endl;}return 0;
}LL inv(LL a,LL n)//求逆运算，参考《训练指南》
{LL d,x,y;gcd(a,n,d,x,y);return d==1?(x+n)%n:-1;
}void gcd(LL a,LL b,LL& d,LL& x,LL& y)//扩展欧几里得算法
{if(!b){d=a;x=1;y=0;}else{gcd(b,a%b,d,y,x);y-=x*(a/b);}
}int dfs(int r)
{int num=0;for(int i=0;i<Tree[r].size();++i){num+=dfs(Tree[r][i]);}vis[r]=1;s[r]=num+1;return s[r];
}

这篇关于UVa 11174 Stand in a Line的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---