boj7737.cpp

#include <iostream>
using namespace std;
#define MAXN 100000
#define FOR(I, A, B) for(int I = (A) ; I <= (B); I++)
#define ll long long
int M, catalan[MAXN+1];
int prime[2*MAXN+1], primes[2*MAXN+1], factor[2*MAXN+1], pc;

//에라테네스 체
void seive(int N){
    int len = 2*N;
    FOR(i, 2, len) { prime[i] = 1, factor[i] = i; }
    FOR(i, 2, len) if(prime[i]){
        if(len/i < i) break;
        int j = i * i;
        while(j <= len){prime[j] = 0; factor[j] = i; j += i; }
    }
    pc = 0;
    FOR(i, 2, len) if(prime[i]){
        prime[i] = ++pc;
        primes[pc] = i;
    }
};
// (a^n)%M을 O( log n)에 계산하는 함수
int expmod(int a, int n){
    if(!n) return 1;
    int d = expmod(a, n/2);
    ll dd = ((ll)d*d)%M;
    if(n%2)
        return (dd*a)%M;
    return (int)dd;
}
struct BinaryTree{
    int tree[2*MAXN+1], leaf[2*MAXN+1], size;
    BinaryTree(int pc){
        init(pc);
    }
    void init(int pc){
        size = 1;
        while(size <= pc) size <<= 1;
        FOR(i, 1, 2*size-1) tree[i] = 1;
    }
    void multiply(int x, int diff){
        //곱하는 수가 들어오면 소인수 분해한 뒤 각 소인수를 인덱스트리에 삽입한다.
        while(x>1){
            int v = factor[x];
            insert(prime[v], diff);
            x /= v;
        }
    }
    void insert(int x, int diff){
        //인덱스 트리에 삽입
        int v = size+x;
        leaf[v] += diff;
        tree[v] = expmod(primes[x] , leaf[v]);
        while(v != 1){
            v/=2;
            tree[v] = int(((ll)tree[v*2]*tree[v*2+1])%(ll)M);
        }
    }
    int getTop(){
        return tree[1];
    }
};
int main(){
    int N;
    ll sum = 0;
    cin >> N >> M;
    seive(N);
    catalan[0] = 1;
    BinaryTree bt = BinaryTree(pc);
    for(int i = 1; i<= N-2; i++){
        int n = i-1;
        
        //관계식 Cn+1 = 2*(2n+1)/(n+2) * Cn을 이용해서 계산하는 부분
        bt.multiply(2, 1);
        bt.multiply(2*n+1, 1);
        bt.multiply(n+2, -1);
        catalan[i] = bt.getTop();
        sum = (sum+catalan[i])%(ll)M;
    }
    cout << sum;
    return 0;
}