同步:https://buringstraw.win/index.php/archives/24/
题目:有趣的数列
描述
我们称一个长度为2n的数列是有趣的,当且仅当该数列满足以下三个条件:
(1)它是从1到2n共2n个整数的一个排列{Ai};
(2)所有的奇数项满足A1<A3<…<A2n-1,所有的偶数项满足A2<A4<…<A2n;
(3)任意相邻的两项A2i-1与A2i(1≤i≤n)满足奇数项小于偶数项,即:A2i-1<A2i。
现在的任务是:对于给定的n,请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大,所以只要求输出答案 mod P的值。
輸入
用空格隔开的两个整数 n 和 P。
輸出
仅含一个整数,表示不同的长度为2n的有趣的数列个数mod P的值
輸入範例 1
3 10
輸出範例 1
5
輸入範例 2
10 1013
輸出範例 2
588
輸入範例 3
675546 14358205
輸出範例 3
1511390
提示
对于样例1:对应的5个有趣的数列分别为
(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%的数据满足n≤1000 ,100%的数据满足n≤1000000且P≤1000000000。
思路
首先发现它是个卡特兰数
-
硬算前几项的数字规律(我是这样做的)
-
可以转换为一个典型的卡特兰数的例子:
n个数排成两行,使右边都大于左边,后边都大于前边,求排法数量
将奇数看成第一行,将偶数看成第二行即可。
然后发现数据很大,递推式都有除法,p也不是质数不能用逆元(虽然我也不回逆元我太弱了)
所以要用这个通项式
\[ f(n)=\frac{C\begin{matrix} n\\ 2n \end{matrix}}{n+1} \]
化一下
\[ 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)!} \]
这样化的作用是可以用特殊的方法约分
枚举1~2n的所有素数
然后分别计算\(n,(n+1),2n\)中那个素数的次数(cnt1,cnt2,cnt3)
再往答案中加乘上\(primes_i^{(cnt3-cnt2-cnt1)}\)就好了
注意这里是乘不是加我就是这样错的
Code
//I closed myself.What a happy zero-boomed contest!!! //上一行是考试自闭的时候写的不要管 //(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);//质数筛 LL qkpow(LL x,LL y);//快速幂 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];//当前质因子次数+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; }
转载于:https://www.cnblogs.com/buringstraw/p/10384824.html
今天的文章洛谷P3200 [HNOI2009]有趣的数列分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/12343.html