题解 P3200 【[HNOI2009]有趣的数列】

· · 题解

洛谷上很多省选题都没有题解，不得不找bzoj的题解

概述

50%

使用递推，在O(n^2)的时间内得到答案，不过我没写对。

正解

通过暴力或者上述方法，打印出较小的答案，可能会发现规律。实际上这题就是求Catalan数(n-2)，有很多理解方式，常见的求法有三种（参见百度百科 ）：

  1. f_n=\sum\limits_{i=0}^{n-1}f_i*f_{n-i-1}$ ，不能使用这个公式，因为也需要$O(n^2)

如果不熟悉组合数的求法，可以做一下计算系数 ，总结中给出代码。

其中\frac{C_{2n}^{n}}{n+1}=\frac{\prod\limits_{i=n+2}^{2n}i}{\prod\limits_{i=1}^ni}，我们需要把所有2n之内的质数筛出来，同时得到每个数最小的质因数（欧拉线性筛法），进行约分再使用快速幂[^qpow]得出结果。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
//注意是2*n
int mp[N],p[N/10],cnt[N],r;
//mp[]表示每个数最小的质因数，p[]表示质数表，cnt[]用于计算指数，r为取模数
int qpow(int a,int b)
//快速幂：计算a^b%r
{
    int ans=1;
    do
    {
        if(b&1)
            ans=(long long)ans*a%r;
        a=(long long)a*a%r;
    }
    while(b/=2);
    return ans;
}
int main()
{
    int n;
    cin>>n>>r;
    int pn=0;
    for(int i=2;i<=2*n;i++)
    {
        if(!mp[i])
        {
            p[++pn]=i;
            mp[i]=i;
        }
        for(int j=1;j<=pn&&i*p[j]<=2*n;j++)
        {
            mp[i*p[j]]=p[j];
            if(i%p[j]==0)
                break;
        }
    }
    //欧拉线性筛法
    for(int i=1;i<=n;i++)
        cnt[i]=-1;
      //需要除以分母
    for(int i=n+2;i<=2*n;i++)
        cnt[i]=1;
      //乘以分子
    for(int i=2*n;i>1;i--)
        if(mp[i]<i)
        //如果是合数，向下传递，可以保证O(n)
        {
            cnt[mp[i]]+=cnt[i];
            cnt[i/mp[i]]+=cnt[i];
        }
    int ans=1;
    for(int i=2;i<=2*n;i++)
        if(mp[i]==i)
        //如果是质数计入答案，合数已经处理过了
            ans=(long long)ans*qpow(i,cnt[i])%r;
              //防止中间过程溢出
    cout<<ans<<endl;
    return 0;
}

总结

组合数相关

这题需要求组合数，我总结了一下我知道的组合数取模的求法（P1313模板）：

  1. 使用杨辉三角C_n^0=C_n^n=1 ，C_n^i=C_{n-1}^i+C_{n-1}^{i-1} 代码见这里

  2. 当p是质数时可以得出a的逆元为a^{p-2} ，C_n^0=1 ，C_n^i=C_n^{i-1}\frac{k-i+1}{i} 代码见这里

  3. 当p不是质数时只能用上述方法，筛出质数并约分代码见这里

应该不需要解释吧

时间复杂度分析

在添加数时，也可以先把这个数分解，但应该会降低效率.

而我用的方法筛质数、添加数、向下传递都是O(n)的，最后一步为\pi(n)log n^pi，而\pi(n)\sim\frac{n}{\ln n} ，因此也近似与O(n) .

[^qpow]: 使用分治法在O(\log n)的时间内计算出a^b\mod p