找规律题。。。

　　首先观察样例解释可得。我们只要确定奇数位的情况就行了，并且只要i<=第i个奇数<=2*i-1就是合法的= =

　　然后我就一直在找规律..................

　　最后弃疗跑去看题解....才发现答案不就是卡特兰数吗。。为啥我看半天都没看出来= =

　　由搜索引擎可得，h(n)=C(2*n,n)/(n+1)。。。求组合数的话我写了分解质因数...

　　顺便学(chao)习(xi)了一下黄学长的分解质因数。。我以前写的都是什么鬼QAQ

　　写了个快速幂竟然比直接乘慢orz

1 #include
      
        2 #include
       
         3 #include
        
          4 #define ll long long 5 using namespace std; 6 const int maxn=2000023; 7 bool cant[maxn]; 8 int pri[maxn],num,mn[maxn],sum[maxn]; 9 ll ans;10 int i,j,k,n,m,sxt;11 inline void prerun(int x){12     register int i,j,k;13     for(i=2;i<=x;i++){14         if(!cant[i])pri[++num]=i,mn[i]=num;15         for(k=pri[j=1]*i;k<=x&&j<=num;k=pri[++j]*i){16             cant[k]=1,mn[k]=j;17             if(!(i%pri[j]))break;18         }19     }20 }21 inline void upd(int x,int v){22     while(x>1)23         sum[mn[x]]+=v,x/=pri[mn[x]];24 }25 inline int power(ll a,int b){26     ll c=1;27     while(b){28         if(b&1){c*=a;if(c>=sxt)c%=sxt;}29         a*=a;if(a>=sxt)a%=sxt;30         b>>=1;31     }32     return c;33 }34 int main(){35     scanf("%d%d",&n,&sxt);36     prerun(n<<1);37     for(i=n<<1;i>n;i--)upd(i,1);38     for(;i;i--)upd(i,-1);39     upd(n+1,-1);40     ans=1;41     for(i=1;i<=num;i++){42         ans*=power(pri[i],sum[i]);43         if(ans>=sxt)ans%=sxt;44     }45     printf("%lld\n",ans);46     return 0;47 }
        
       
      

其实那个合法的条件也可以变一下，将数列里的每个数都减去(i-1)之后就是1<=第i个奇数<=i 。。。就是卡特兰数了>_<