网站建设云技术公司推荐,百度竞价广告怎么收费,潍坊网站制作软件,php面试题[HNOI2009]有趣的数列 有一个长度为2n的1~2n的全排列#xff0c;保证其奇数项递增#xff0c;偶数项递增#xff0c;并且相邻的奇数项和偶数项#xff0c;后面的偶数项大于奇数项的方案数\(mod\ p,n1000000,P1000000000\)。 解 注意到2n#xff0c;实际上也就猜到…[HNOI2009]有趣的数列 有一个长度为2n的1~2n的全排列保证其奇数项递增偶数项递增并且相邻的奇数项和偶数项后面的偶数项大于奇数项的方案数\(mod\ p,n1000000,P1000000000\)。 解 注意到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(n1);printf(%d,cat(n));return 0;
}
il void sieve(int n){int i,j;for(i2;in;i){if(!check[i])prime[pt]i;for(j1;jptprime[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(y1)ans(ll)ans*x%yyb;x(ll)x*x%yyb,y1;}return ans;
}
il int cat(int n){int n2(n1),i,j,tr(0),xdk(n1),ans(1);for(i1;ipt;i,tr0){for(jn2;j;j/prime[i])trj/prime[i];for(jn;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;
}转载于:https://www.cnblogs.com/a1b3c7d9/p/10804247.html
