Luogu P3200 [HNOI2009] Interesting Sequence

Problem: Interesting Sequence#

Description#

We call a sequence of length 2n interesting if and only if it satisfies the following three conditions:

(1) It is a permutation {Ai} of the 2n integers from 1 to 2n.

(2) All odd-indexed terms satisfy A1<A3<...<A2n-1, and all even-indexed terms satisfy A2<A4<...<A2n.

(3) Any two adjacent terms A2i-1 and A2i (1≤i≤n) satisfy the condition that the odd-indexed term is less than the even-indexed term, i.e., A2i-1<A2i.

Now the task is to find the number of different interesting sequences of length 2n for a given n. Since the final answer may be large, only output the value of the answer mod P.

Input#

Two integers n and P separated by a space.

Output#

Only one integer, representing the value of the number of different interesting sequences of length 2n mod P.

Example Input 1#

3 10

Example Output 1#

Example Input 2#

10 1013

Example Output 2#

Example Input 3#

675546 14358205

Example Output 3#

Note#

For example 1: The corresponding 5 interesting sequences are

(1,2,3,4,5,6), (1,2,3,5,4,6), (1,3,2,4,5,6), (1,3,2,5,4,6), (1,4,2,5,3,6).

50% of the data satisfies n≤1000, and 100% of the data satisfies n≤1000000 and P≤1000000000.

Idea#

First, it is found that it is a Catalan number.

Calculate the digital pattern of the first few terms (this is what I did)
It can be transformed into a typical example of Catalan numbers:

Arrange n numbers into two rows, so that the numbers on the right are greater than those on the left, and the numbers on the back are greater than those on the front, and calculate the number of arrangements

Treat odd numbers as the first row and even numbers as the second row.

Then it is found that the data is very large, and the recurrence formulas all have divisions, and p is not a prime number, so the inverse element cannot be used (~~although I don't know the inverse element, I am too weak~~)

So we need to use this general formula

f(n)=\frac{C\begin{matrix} n\\ 2n \end{matrix}}{n+1}

Simplify it

f(n)=\frac{C\begin{matrix} n\\ 2n \end{matrix}}{n+1} \\ =\frac{(2n)!}{n!\cdot n!\cdot (n+1)}\\ =\frac{(2n)!}{n!\cdot (n+1)!}

This simplification allows for special cancellation.

Enumerate all prime numbers from 1 to 2n

Then calculate the number of times the prime number appears in $n,(n+1),2n$(cnt1,cnt2,cnt3)

Then add $primes_i^{(cnt3-cnt2-cnt1)}$ to the answer

Note that this is multiplication, not addition. I made this mistake.

Code#

//I closed myself.What a happy zero-boomed contest!!!
//The line above was written when I was self-closing during the exam. Please ignore it.
//(2n)!/(n!*n!*(n+1))
#include<bits/stdc++.h>
#define LL long long
using namespace std;

const LL MAXN=1000000+5;

LL n,p,cnt;
bool v[MAXN];
LL primes[2*MAXN];
bool isHeshu[2*MAXN];

LL oula(LL x);//Prime number sieve
LL qkpow(LL x,LL y);//Fast power

int main(){
//	freopen("LLeresting.in","r",stdin);
//	freopen("LLeresting.out","w",stdout);
	
	scanf("%d%d",&n,&p);
	oula(2*n);
	LL ans=1;
	for(LL i=1;i<=cnt;++i){
		LL cnt1=0,cnt2=0,cnt3=0;
		LL pm=primes[i];
		while(pm<=2*n){
			cnt1+=n/pm;
			cnt2+=(n+1)/pm;
			cnt3+=2*n/pm;
			pm*=primes[i];//Current prime factor count +1
		}
		LL sl=cnt3-cnt1-cnt2;
		ans*=qkpow(primes[i],sl);
		ans%=p;
	}
	printf("%lld\n",ans);
	
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

LL oula(LL x){
	for(LL i=2;i<=x;++i){
		if(!isHeshu[i]){
			primes[++cnt]=i;
		}
		for(LL j=1;primes[j]*i<=x;++j){
			isHeshu[primes[j]*i]=1;
			if(i%primes[j]==0)break;
		}
	}
}

LL qkpow(LL x,LL y){
	LL sum=x;
	LL ret=1;
	while(y){
		if(y&1){
			ret=ret*sum%p;
		}
		sum=sum*sum%p;
		y>>=1;
	}
	return ret;
}