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 elements satisfy A1<A3<...<A2n-1, and all even-indexed elements satisfy A2<A4<...<A2n.

(3) Any two adjacent elements A2i-1 and A2i (1≤i≤n) satisfy that the odd-indexed element is smaller than the even-indexed element, i.e., A2i-1<A2i.

Now the task is: for a given n, calculate the number of different interesting sequences of length 2n. 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, we find that it is a Catalan number.

Calculate the numerical 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 in the back are greater than those in the front. Calculate the number of arrangements.

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

Then we find that the data is very large, and the recurrence formulas all involve division. Since p is not a prime number, we cannot use the inverse element (~~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)!}

The purpose of this simplification is to be able to cancel out some terms using a special method.

Enumerate all prime numbers from 1 to 2n.

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

Then multiply the answer by $primes_i^{(cnt3-cnt2-cnt1)}$ and add it to the answer.

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

Code#

//I closed myself.What a happy zero-boomed contest!!!
//The previous line was written when I was having a mental breakdown 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 exponentiation

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;
}