HDU 5673 Robot 卡特兰数-白红宇

HDU 5673 Robot 卡特兰数

阅读量：5855 次

发布时间：2019-06-19

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

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=5673

　　题目描述：一个人从原点开始向右走，要求N秒后回到原点，且过程中不能到负半轴，人有两种操作，走动或者停止，问总共有多少种方案？

　　解题思路：类似于括号匹配问题，和那个我去年这个时候接触到的最裸的不能越过对角线的正方形走到对角问题，卡特兰数，从2开始枚举走动步数，然后剩下的就是不动的步数，用不动的步数做个填充就可以了，设计到取模，需要逆元

　　代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define mem0(a) memset(a,0,sizeof(a))#define meminf(a) memset(a,-0x3f,sizeof(a))#define fi(n) for(i=0;i

View Code

　　思考：很裸的卡特兰数，组合数学很有意思，然后就是说我感觉现在需要开始整理一下板子了，比如说这个，还有那个神题等等，洗完澡回来再说，我好菜啊

http://acm.hdu.edu.cn/showproblem.php?pid=5673

转载于:https://www.cnblogs.com/FriskyPuppy/p/7429331.html

你可能感兴趣的文章