UVA11174vector实现树的搜索和使用逆元求a/b%n-白红宇的个人博客

发布日期：2021-10-08 15:48:51 浏览次数：11 分类：技术文章

本文共 1258 字，大约阅读时间需要 4 分钟。

考虑一棵以C为根的子树，cj为其孩子，首先每棵以孩子节点为根的子树的排列是相互独立的，满足乘法原理，所以在不考虑子树之间的排列时排列总数为∏f(cj),再考虑吧所有的子孙穿插起来(其中每棵子树子孙的相对位置不变)的排列数，这相当于有重复元素的全排列，所以f(C) = f(c1)*f(c2)...f(cj)*(s(C)-1)!/(s(c1)!s(c2)!...s(cj)!)，通过递归式的求解可以化简成为f(root) = (s(root)-1)!/(s(1)!s(2)!...s(n)!)，此题要求答案对1000000007取模后的结果，把除法转化成乘以其逆元，所以预处理从1到40000阶乘和其在⊙m下的乘法逆元，m = 1000000007，按照给出的数据带入即可,所谓逆元，既可以求a/b%n转换为a*b^-1%n,此处b^-1并不是表示次方，而是逆元的意思，下面给出本题代码，其中有求逆元的代码，至于具体的理解可以参考大白书或者小白书：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #define LL long long#define Mod 1000000007using namespace std;const int N=40005;int t,n,m;LL fac[N],inv[N];LL cnt[N];vector 
              
               
                 > v;void exgcd(LL a,LL b,LL &x,LL &y,LL &d){ if(b==0) { d=a; x=1; y=0; } else { exgcd(b,a%b,y,x,d); y-=x*(a/b); }}LL inverse(LL a,LL M){ LL x,y,d; exgcd(a,M,x,y,d); return d==1?(x+M)%M:-1;}void init(){ fac[0]=1; for(int i=1;i<=40000;i++) { fac[i]=fac[i-1]*i%Mod; inv[i]=inverse(i,Mod); }}void initial(){ for(int i=0;i<=n;i++) cnt[i]=-1; v.clear();}void intput(){ int x,y; v.resize(n+1); while(m--) { cin>>x>>y; v[y].push_back(x); }}LL dfs(int x){ if(cnt[x]!=-1) return cnt[x]; int c=1; for(LL i=0;i
                
                 >t; while(t--) { cin>>n>>m; initial(); // cout<
                 
                  <

转载地址：https://blog.csdn.net/ONE_PIECE_HMH/article/details/45566621 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：UVA LA3516,分支法加上递归和递推

下一篇：uva11137递推和DP其实有些类似

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章