HNOI 2009 有趣的数列

洛谷 P3200 [HNOI2009]有趣的数列

洛谷传送门

JDOJ 2130: [HNOI2009]有趣的数列 D1 T3

JDOJ传送门

Description

我们称一个长度为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的值。

Input

输入文件只包含用空格隔开的两个整数n和P。输入数据保证,50%的数据满足n≤1000,100%的数据满足n≤1000000且P≤1000000000。

Output

仅含一个整数,表示不同的长度为2n的有趣的数列个数mod P的值。

Sample Input

3 10

Sample Output

5

HINT

对应的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)。

Source

HNOI2009

最优解声明

HNOI 2009 有趣的数列

题解:

模拟赛T1爆零题。

暴力打表看一下可以发现:这道题当n=1、2、3、4、5时,答案分别等于:1、2、5、14、42......

根据出题人@\(JZYshuraK\)的解说,看到这应该马上看出规律。然而本蒟蒻太菜了

这明明就是卡特兰数么?

所以这道题就变成了求第n项卡特兰数模mod。

根据卡特兰数的递推式,常用的计算卡特兰数的递推公式有以下几种:
\[ f(n)=\sum^{n-1}_{i=0}f(i)\times f(n-i-1) \]

\[ f(n)=f(n-1)\times \frac{4n-2}{n+1} \]

\[ f(n)=\frac{C^{2n}_n}{n+1} \]

(以上知识不会请自行补习...)

第一个公式的时间复杂度是\(O(n^2)\)的。比暴力好不了多少。

第二个公式和第三个公式用不了,因为模数和除数不一定互质,无法进行乘法逆元的运算。

但其实是可以用的,第三个公式可以通过把组合数展开:
\[ C_n^m=\frac{n!}{m!(n-m)!} \]
以上是组合数公式。

可以化为:
\[ \frac{C_{2n}^{n}}{n+1}=\frac{(2n)!}{n!\times (n+1)!} \]
下面就是这个东西如何去取模的问题。

隆重介绍一种分数取模的方法(乘法逆元固然是最常用的):质因数分解约分法。

很简单,因为上面的都是阶乘,所以有很多相同项是可以被约去的。

所以我们先预处理出一个\(1-2n\)的质数表,然后按这个依次合并就好。

代码:

#include<stdio.h>
#define ll long long
#define int long long
ll n,mod,cnt;
ll ans=1,temp,m;
int prime[1000000<<2],a[1000000<<2];
void euler(int x)
{
    for(int i=2;i<=x;i++)
    {
        if(!a[i])
            a[i]=prime[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if(prime[j]>a[i] || prime[j]>x/i)
                break;
            a[i*prime[j]]=prime[j];
        }
    }
}
ll qpow(ll a,ll b)
{
    ll ret=1;
    while(b>0)
    {
        if(b&1)
            ret=(ret*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ret;
}
signed main()
{
    scanf("%lld%lld",&n,&mod);
    int p=n*2;
    euler(p);
    for(int i=1;i<=cnt;i++)
    {
        temp=0;
        m=n*2;
        while(m>0)
        {
            m=m/prime[i];
            temp=temp+m;
        }
        m=n;
        while(m>0)
        {
            m=m/prime[i];
            temp=temp-m;
        }
        m=n+1;
        while(m>0)
        {
            m=m/prime[i];
            temp=temp-m;
        }
        ans=(ans*qpow(prime[i],temp))%mod;
    }
    printf("%lld",ans);
    return 0;
}
上一篇:【HNOI 2019】JOJO


下一篇:HNOI 排队