LOJ 10239 有趣的数列

首先可以将奇数视作入栈，偶数视作出栈，那么它是卡特兰数，其实打表也能看出来，而且好像可以用dp？

不过这道题的难点不在这里，p不是素数，所以不能用求逆元来做，不过前50%的分可以用杨辉三角+达标拿到，之后的分就要用到质因数分解了。

求卡特兰数的公式：$h[n]=\frac{C_{2n}^n}{n+1}$,化简之后将其分解，一开始我并没有按质因数分解，结果T了，分解质因数要更快一点。

 void add(int x,int nu)

 {

     for(int i=;prime[i]*prime[i]<=x;i++)

     while(x%prime[i]==)

     {

         cnt[prime[i]]+=nu;

         x/=prime[i];

     }

     cnt[x]+=nu;

 }

 for(int i=n+;i<=*n;i++)add(i,);

     for(int i=;i<=n;i++)add(i,-);

     LL ans=;

     for(int i=;i<=*n;i++)

         for(int j=;j<=cnt[i];j++)

             ans=ans*i%p;

代码实现

 #include<iostream>

 #include<cstdio>

 #define LL long long

 //#define int LL

 using namespace std;

 int n,p;

 int cnt[];

 int prime[],num;

 bool isprime[];

 #define N 20000

 void s()

 {

     for(int i=;i<=N;i++)isprime[i]=;

     for(int i=;i<=N;i++)

     {

         if(isprime[i])prime[++num]=i;

         for(int j=;j<=num&&i*prime[j]<=N;j++)

         {

             isprime[i*prime[j]]=;

             if(!i%prime[j])break;

         }

     }

 }

 void add(int x,int nu)

 {

     for(int i=;prime[i]*prime[i]<=x;i++)

     while(x%prime[i]==)

     {

         cnt[prime[i]]+=nu;

         x/=prime[i];

     }

     cnt[x]+=nu;

 }

 signed main()

 {

     s();

     cin>>n>>p;

     for(int i=n+;i<=*n;i++)add(i,);

     for(int i=;i<=n;i++)add(i,-);

     LL ans=;

     for(int i=;i<=*n;i++)

         for(int j=;j<=cnt[i];j++)

             ans=ans*i%p;

     cout<<ans<<endl;

 }

完整代码

巴特西

LOJ 10239 有趣的数列

最新文章

热门文章