[HNOI2009]有趣的数列卡特兰数

题面：[HNOI2009]有趣的数列

题解：

　　观察到题目其实就是要求从长为2n的序列中选n个放在集合a，剩下的放在集合b，使得集合a和集合b中可以一一对应的使a中的元素小于b。

　　2种想法（实质上是一样的）。

　　1，相当于前1位中至少要选1个放入a，前3位中至少要选2位放入a，前5位中至少要选3位放入a......前2n - 1位中恰好选n位放入a。

　　2，用0表示放入a集合，1表示放入b集合。则每个1都必须有一个左边的0与之匹配，相当于对于任意位置前面0的个数大于等于1的个数。

　　不管是哪种，其实都可以看做括号匹配问题。。。。。。所以就是卡特兰数了

　　因为n比较大，且p不一定为质数，因此可以用一个数组存下每个质因子有几个，对于乘法就累加，除法就减掉，然后把最后剩下的累乘起来就是答案。

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 2001000

 #define maxn 2000000

 #define LL long long

 int tot, n, p;

 int pri[AC], last[AC];

 LL have[AC], ans;

 bool ispri[AC];

 void get()

 {

     last[] = ;

     for(R i = ; i <= maxn; i ++)

     {

         if(!ispri[i]) pri[++ tot] = i, last[i] = i;

         for(R j = ; j <= tot; j ++)

         {

             int now = pri[j];

             if(i * now > maxn) break;

             ispri[i * now] = true, last[i * now] = now;

             if(!(i % now)) break;

         }

     }

 }

 void pre(){

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

 }

 inline void cal(int x){//分解质因数

     while(last[x] != ) ++ have[last[x]], x /= last[x];

 }

 inline void cut(int x){

     while(last[x] != ) -- have[last[x]], x /= last[x];

 }

 inline LL qpow(LL x, int have)

 {

     LL ans = ;

     while(have)

     {

         if(have & ) ans = ans * x % p;

         x = x * x % p, have >>= ;

     }

     return ans;

 }

 void work()

 {

     int b =  * n;

     for(R i = ; i <= b; i ++) cal(i);

     for(R i = ; i <= n; i ++) cut(i), cut(i);

     cut(n + ), ans = ;

     for(R i = ; i <= b; i ++)

         if(have[i]) ans = ans * qpow(i, have[i]) % p;

     printf("%lld\n", ans);

 }

 int main()

 {

 //    freopen("in.in", "r", stdin);

     get();

     pre();

     work();

 //    fclose(stdin);

     return ;

 }

巴特西

[HNOI2009]有趣的数列卡特兰数

最新文章

热门文章

巴特西

[HNOI2009]有趣的数列 卡特兰数

最新文章

热门文章

[HNOI2009]有趣的数列卡特兰数