简单prufer应用-白红宇

简单prufer应用

阅读量：5874 次

发布时间：2019-06-19

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

【bzoj1005】

Description

　　自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在

任意两点间连线,可产生多少棵度数满足要求的树?

Input

　　第一行为N(0 < N < = 1000),

接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

Output

　　一个整数,表示不同的满足要求的树的个数,无解输出0

Sample Input

-1

Sample Output

关于prufer序列这个定理的证明，

给出大佬博客http://hzwer.com/3272.html

我这里就给一个结论

写到代码里，OK！

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define il inline#define re registerusing namespace std;const int N=1111;int n,m,p,d[N],ans[N],chk[N],pr[N],cnt[N],tot,l;il void filt(){ for(int i=2;i<=1000;i++) if(!chk[i]){ pr[++tot]=i; for(int j=i+i;j<=1000;j+=i) chk[j]=1; }}il void add(int p,int v){// cout<<<"...\n"; for(int k=1;k<=p;k++){ int x=k; for(int i=1;i<=tot;i++){ if(x<=1) break; while(x%pr[i]==0){ cnt[i]+=v;x/=pr[i]; } } }}il void mul(int x){// cout<
                 
                  <
                  
                   0){ l++; ans[l+1]+=ans[l]/1000000; ans[l]%=1000000; }}int main(){ filt(); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&d[i]); } if(n==1){ if(!d[1]) cout<<'1'; else cout<<'0'; return 0; } for(int i=1;i<=n;i++){ if(!d[i]){ printf("0"); return 0; } if(d[i]==-1) m++; else{ d[i]--;p+=d[i]; } } if(p>n-2){ printf("0"); return 0; } add(n-2,1); add(n-2-p,-1); for(int i=1;i<=n;i++) if(d[i]>0) add(d[i],-1); ans[1]=1;l=1;/* for(int i=1;i<=tot;i++) cout<
                   
                    <<' '; cout<
                    
                     =1;i--) printf("%06d",ans[i]); return 0;}

【bzoj1430】

Description

一开始森林里面有N只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过N-1次打架之后，整个森林的小猴都会成为好朋友。现在的问题是，总共有多少种不同的打架过程。比如当N=3时，就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。

Input

一个整数N。

Output

一行，方案数mod 9999991。

Sample Input

Sample Output

HINT

50%的数据N<=10^3。

100%的数据N<=10^6。

【soltuion】

这不是刚刚那题的弱弱弱化版？

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #define il inline#define re register#define mod 9999991using namespace std;typedef long long ll;int n,ans=1;int main(){ scanf("%d",&n); for(int i=1;i<=n-2;i++) ans=(ll)ans*n%mod; for(int i=1;i

我不会告诉你这篇博客只是一个刷题记录

转载于:https://www.cnblogs.com/ExiledPoet/p/7070530.html

你可能感兴趣的文章