UVA 11174 Stand in a Line，UVA 1436 Counting heaps —

　　这两个题的模型是有n个人，有若干的关系表示谁是谁的父亲，让他们进行排队，且父亲必须排在儿子前面（不一定相邻）。求排列数。

　　我们假设s[i]是i这个节点，他们一家子的总个数（或者换句话说，等于他的子孙数+1（1是他本身）），f[i]是以i为根的节点的排列种数。那么总的种数为n!/(s[1]+s[2]+...+s[n])。关于这个递推式的得出，是根据排列公式的，我们假设一个例子，不妨设4.5是2的子孙，3是1的子孙。那么他们进行排队的话，不妨看成222和11排队就是2的家族和1的家族排队（2和1是平行关系）。那么他们如果真的是全部一样的话，排列数为5！/（2！*3！）。然后再根据他们自身有的排列种数，不妨设为f[2],f[1]，那么总的排列数为他们相乘，即：f[2]*f[1]*5！/（2！*3！）。因此，推广开来对于一个节点i（这里看做是2,1的父亲），那么以节点i为根的子节点的排列数为：f[i]=f[c1]*f[c2]*...*d[ck]*(s[i]-1)!/(s[c1]!*s[c2]!*...*s[ck]!)，其中这c1到ck代表这他的若干个儿子，如果将每个f都进行同样的递推，一直到这个节点是一个点为止，这样可以消去所有的f（因为一个点的排序种数就是1），这样子的话，可以化成f[i]=(s[i]-1)!/(s[1]+s[2]+...+s[ck])，对所有点，用一个虚拟节点0当做父亲，这样，得到f[0]=(s[0]-1)!/(s[1]+s[2]+...+s[n])。考虑到s[0]=n+1，因此得到上面的公式。

　　得到这个公式以后，下面的代码都顺理成章了。第一题用的是求逆元，因为mod的是一个素数，而第二题不是，所以用的是分解质因数。第二题是一个很好的题，涉及到了很多知识点，还包括了非递归的求一棵树的每个节点的包含的子节点的个数的方法（即上面的s，当然，前面的说法不准确，加上1才是上面的s）。

　　具体见代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <iostream>

 #include <vector>

 using namespace std;

 const int mod = ;

 typedef long long ll;

 const int N = +;

 vector<int> G[N];

 int n,m,s[N];

 int in[N];

 ll fac[N],inv[N];

 ll qpow(ll x,ll n)

 {

     ll ans = ;

     while(n)

     {

         if(n&) ans = (ans*x) % mod;

         n >>= ;

         x = (x*x) % mod;

     }

     return ans;

 }

 void init()

 {

     for(int i=;i<=n;i++) G[i].clear();

     memset(in,,sizeof(in));

     memset(s,,sizeof(s));

 }

 void get()

 {

     fac[]=inv[]=;

     for(int i=;i<=;i++)

     {

         fac[i] = (fac[i-]*i)%mod;

         inv[i] = qpow(i,mod-);

     }

 }

 int dfs(int x)

 {

     int& ans = s[x];

     ans = ;

     for(int i=;i<G[x].size();i++)

     {

         int v = G[x][i];

         ans += dfs(v);

     }

     return ans;

 }

 int main()

 {

     get();

     int T;

     scanf("%d",&T);

     while(T--)

     {

         init();

         scanf("%d%d",&n,&m);

         while(m--)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             G[v].push_back(u);

             in[u] ++;

         }

         for(int i=;i<=n;i++)

         {

             if(!in[i]) dfs(i);

         }

         ll ans = fac[n];

         for(int i=;i<=n;i++) ans = (ans*inv[s[i]]) % mod;

         cout<<ans<<endl;

     }

 }

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <iostream>

 #include <vector>

 using namespace std;

 const int mod = ;

 typedef long long ll;

 const int N = +;

 vector<int> G[N];

 int n,m,s[N];

 bool vis[N];

 ll fac[N],inv[N];

 ll qpow(ll x,ll n)

 {

     ll ans = ;

     while(n)

     {

         if(n&) ans = (ans*x) % mod;

         n >>= ;

         x = (x*x) % mod;

     }

     return ans;

 }

 void init()

 {

     for(int i=;i<=n;i++) G[i].clear();

     memset(vis,false,sizeof(vis));

     memset(s,,sizeof(s));

 }

 void get()

 {

     fac[]=inv[]=;

     for(int i=;i<=;i++)

     {

         fac[i] = (fac[i-]*i)%mod;

         inv[i] = qpow(i,mod-);

     }

 }

 int dfs(int x)

 {

     int& ans = s[x];

     if(ans != ) return ans;

     ans = ;

     vis[x] = true;

     for(int i=;i<G[x].size();i++)

     {

         int v = G[x][i];

         ans += dfs(v);

     }

     return ans;

 }

 int main()

 {

     get();

     int T;

     scanf("%d",&T);

     while(T--)

     {

         init();

         scanf("%d%d",&n,&m);

         while(m--)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             G[v].push_back(u);

         }

         for(int i=;i<=n;i++)

         {

             if(!vis[i]) dfs(i);

         }

         ll ans = fac[n];

         for(int i=;i<=n;i++) ans = (ans*inv[s[i]]) % mod;

         cout<<ans<<endl;

     }

 }

上面两题都是递归求s的方法，第一种是根据入度来求，第二种是根据记忆化搜索来求。

　　第二题的代码如下，第二题的代码注释很详细，值得好好研究。代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <iostream>

 #include <vector>

 #include <queue>

 using namespace std;

 typedef long long ll;

 const int N = +;

 int n,mod;

 bool isprime[N];

 int prime[N],tot=,fa[N],cnt[N],vis[N];

 void getPrimeTable()

 {

     memset(isprime,true,sizeof(isprime));

     for(int i=;i<N;i++)

     {

         if(isprime[i])

         {

             prime[++tot] = i;

             for(ll j=(ll)i*i;j<(ll)N;j+=i)

             {

                 isprime[j]=false;

             }

         }

     }

 }

 ll qpow(ll x,ll n)

 {

     ll ans = ;

     while(n)

     {

         if(n&) ans = (ans*x) % mod;

         n >>= ;

         x = (x*x) % mod;

     }

     return ans;

 }

 void getNode() // 这里用bfs的方法从子节点到根节点倒序统计出每个节点所包含的子节点的数目

 {

     memset(cnt,,sizeof(cnt)); // 这里cnt表示的是每个节点所包含的节点的数目

     queue<int> Q;

     for(int i=;i<=n;i++)

     {

         if(!vis[i]) Q.push(i); // 如果该节点出度为0，则是叶子节点，加入队列

     }

     while(!Q.empty())

     {

         int x = Q.front();Q.pop();

         cnt[x] += ; // 该叶子节点本身也算在内

         cnt[fa[x]] += cnt[x]; // 父亲节点数增加该节点的节点数

         vis[fa[x]] --; // 父亲节点的出度减1

         if(!vis[fa[x]]) Q.push(fa[x]);

     }

 }

 void init()

 {

     memset(vis,,sizeof(vis));

     for(int i=;i<=n;i++)

     {

         scanf("%d",fa+i);

         vis[fa[i]] ++; // 这里vis表示的是该点的出度

     }

     getNode();

     memset(vis,,sizeof(vis)); // 这里vis重新用于记载某个分母中某个因子存在的个数

     for(int i=;i<=n;i++) // 因为s[i]的数目最大不会超过n

         vis[cnt[i]] ++;

 }

 void cal(int u,int dt) // 用于分解质因数的计算

 {

     for(int i=;i<=tot;i++)

     {

         int k = prime[i];

         while(u%k == )

         {

             cnt[k] += dt;

             u /= k;

         }

         if(isprime[u]) // 如果u已经是质数了，就可以返回了

         {

             cnt[u] += dt;

             return;

         }

     }

 }

 ll solve()

 {

     memset(cnt,,sizeof(cnt)); // 这里cnt重新用于记录分数上下约分以后每个质因数的个数

     for(int i=;i<=n;i++) cal(i,); // 对n的阶乘的计算

     for(int i=;i<=n;i++)

     {

         if(vis[i]) cal(i,-vis[i]); // 对分母的计算

     }

     ll ans = ;

     for(int i=;i<=tot;i++)

     {

         int k = prime[i];

         if(cnt[k]) ans = (ans*qpow(k,(ll)cnt[k])) % mod;

     }

     return ans;

 }

 int main()

 {

     getPrimeTable();

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&mod);

         init();

         cout<<solve()<<endl;

     }

 }

另外值得注意的是，线性筛素数的方法。

巴特西

UVA 11174 Stand in a Line，UVA 1436 Counting heaps —— （组合数的好题）

最新文章

热门文章