luogu P3200 [HNOI2009]有趣的数列|Catalan数|数论

saitoasuka 2019-02-15 原文

luogu P3200 [HNOI2009]有趣的数列|Catalan数|数论
Problem
分析
Code

luogu P3200 [HNOI2009]有趣的数列|Catalan数|数论

Problem

分析

分析题目可得：

答案取模前就是Catalan数：
\[
ans(取模前)=\frac{C_{n}^{2n}}{\left(n+1\right)}=\frac{2n!}{n!(n+1)!}
\]
根据n的范围：[0,1e6]可知超long long

所以题目给出p来膜

众所周知，带有除法的式子是不能直接每一步进行求余的

这时候可能会想到逆元。

众所周知，逆元中膜的数是质数

所以逆元也不行。

众所周知，ans(取模前)一定是整数，观察ans表达式：

如果对2n!进行整数唯一分解，即：
\[
2n!=a_1^{b_1}\cdot a_2^{b_2}\cdot a_3^{b_3}\cdot…\cdot a_i^{b_i}
\]
同理对n!和(n+1)!进行整数唯一分解，

如果2n!和n!与(n+1)!有相同分解ai,则2n!中次数一定大于n!和(n+1)!的次数(因为ans是整数)

所以ans可以进一步化解：
\[
ans=a_1^{b_1-b_1′-b_1”}\cdot a_2^{b_2-b_2′-b_2”}\cdot a_3^{b_3-b_3′-b_3”}\cdot a_i^{b_i-b_i’-b_i”}
\]
于是问题变成对阶乘进行整数唯一分解

对阶乘n!进行整数唯一分解的方法：
\[
\exists 质数m_i\in[2,n!],cnt[m_i]=n/m_i+n/m_i^2+n/m_i^3+…+n/m_i^k,m^k\leqslant n
\]
综上所述，程序分为三个部分：

1、欧拉筛求质数

2、快速幂

3、进行catalan计算

Code

1、欧拉筛求质数

void Euler(ll n){
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=0;
    for(ll i=2;i<=n;i++){
        if(isprime[i]) m[++cnt]=i;
        for(ll j=1;i*m[j]<=n;j++){
            isprime[i*m[j]]=0;
            if(i%m[j]==0) break;
        }
    }
}

2、快速幂

ll qpow(ll a,ll b){
    ll ans=1,base=a;
    while(b){
        if(b&1) ans=ans*base%p;
        base=base*base%p;
        b>>=1;
    }
    return ans%p;
}

3、求Catalan数

ll catalan(ll n){
    ll ans=1;
    for(ll i=1;i<=cnt&&m[i]<=2*n;i++){
        ll cnt1=0,cnt2=0,cnt3=0;
        ll pm=m[i];
        while(pm<=2*n){
            cnt1+=2*n/pm,cnt2+=n/pm,cnt3+=(n+1)/pm;
            pm*=m[i];
        }
        ans=ans*qpow(m[i],cnt1-cnt2-cnt3)%p;
    }
    return ans;
}

代码：

/*
C2n-n/(n+1)
=2n!/n!(n+1)
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#define ll long long 
using namespace std;
const int maxn=2e6+5;
ll n,p;
ll isprime[maxn],m[maxn],cnt=0;
ll qpow(ll a,ll b){
    ll ans=1,base=a;
    while(b){
        if(b&1) ans=ans*base%p;
        base=base*base%p;
        b>>=1;
    }
    return ans%p;
}
void Euler(ll n){
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=0;
    for(ll i=2;i<=n;i++){
        if(isprime[i]) m[++cnt]=i;
        for(ll j=1;i*m[j]<=n;j++){
            isprime[i*m[j]]=0;
            if(i%m[j]==0) break;
        }
    }
}
ll catalan(ll n){
    ll ans=1;
    for(ll i=1;i<=cnt&&m[i]<=2*n;i++){
        ll cnt1=0,cnt2=0,cnt3=0;
        ll pm=m[i];
        while(pm<=2*n){
            cnt1+=2*n/pm,cnt2+=n/pm,cnt3+=(n+1)/pm;
            pm*=m[i];
        }
        ans=ans*qpow(m[i],cnt1-cnt2-cnt3)%p;
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&p);
    Euler(2*n);
    printf("%lld",catalan(n));
    return 0;
}