自动搬运

查看原文

来自洛谷，原作者为

	zhzh2001 **

搬运于2025-08-24 21:46:25，当前版本为作者最后更新于2017-03-09 19:25:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷上很多省选题都没有题解，不得不找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)$

2. $f_n=f_{n-1}*\frac{4n-2}{n+1}$ ，我本来以为可以用的，但是由于$p$不一定是一个质数，因此无法计算逆元以进行除法运算

3. $f_n=\frac{C_{2n}^{n}}{n+1}$ ，这是可用的公式

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

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

代码

#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$^[2]，而$\pi(n)\sim\frac{n}{\ln n}$ ，因此也近似与$O(n)$ .