[HNOI2009]有趣的數列

[HNOI2009]有趣的數列

有一個長度為2n的1~2n的全排列，保證其奇數項遞增，偶數項遞增，并且相鄰的奇數項和偶數項，后面的偶數項大于奇數項的方案數\(mod\ p,n<=1000000,P<=1000000000\)。

解

注意到2n，實際上也就猜到它可能為catalan數列了，再看看樣例，\(1,2,5,14\),顯然為catalan數，故可以猜測為catalan數，在套個質因數分解階乘求組合數上去就可以了。

現在在于如何證明，注意到元素不為2個，于是考慮已學模型有多個元素的自然也只有棧，于是考慮去構造棧的模型，因為有遞增的要求，所以入棧序必然要讓其為遞增的，即有1~2n等著去入棧，顯然每次入棧的數要比前面都要大，然而又要想辦法把它壓到n個元素，棧只有n個元素，于是自然會給出兩個容器，一個裝奇數，一個裝偶數，自然奇數容器里面會是遞增的，而偶數容器也一樣，但是問題在于偶數容器里面是否能保證每個偶數都要對應比奇數大，顯然按照我們這種入棧的方式，只要保證任意一次操作偶數入棧的數量比奇數入棧次數少即可，于是也就成功地轉化成了catalan模型。

參考代碼：

#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define ll long long
using namespace std;
bool check[2000001];
int yyb,prime[200000],pt;
il void sieve(int);
il int cat(int),pow(int,int);
int main(){int n;scanf("%d%d",&n,&yyb),sieve(n<<1);printf("%d",cat(n));return 0;
}
il void sieve(int n){int i,j;for(i=2;i<=n;++i){if(!check[i])prime[++pt]=i;for(j=1;j<=pt&&prime[j]<=n/i;++j){check[i*prime[j]]|=true;if(!(i%prime[j]))break;}}
}
il int pow(int x,int y){int ans(1);while(y){if(y&1)ans=(ll)ans*x%yyb;x=(ll)x*x%yyb,y>>=1;}return ans;
}
il int cat(int n){int n2(n<<1),i,j,tr(0),xdk(n+1),ans(1);for(i=1;i<=pt;++i,tr&=0){for(j=n2;j;j/=prime[i])tr+=j/prime[i];for(j=n;j;j/=prime[i])tr-=j/prime[i]<<1;while(!(xdk%prime[i]))xdk/=prime[i],--tr;ans=(ll)ans*pow(prime[i],tr)%yyb;}return ans;
}