填个坑....

Problem

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

线性筛素数

其它博客都有吧...
就解释一下为什么是if(i%prime[j]==0) break;吧。

简单来讲，每个质数一定会被它的最小质因数乘上某个唯一的合数筛去。

例如 $2*2*2*3*3$，一定会是 $2*36$ 筛去。
它不会是 $3*24$ 筛去，因为 $24$ 含有 $2$ 的因子，会被 break 掉。

线性筛素数后分解小数质因数

先说一下，分解大数质因数的方法是 Pollard-Rho，理论效率低于此方法。
我们首先得线性筛。
然后记录每一个数的至少一个非 1 因子。
则迭代除去。
因为一个数 $x$ 的质因子个数 $\leq \log x$，则算法本身复杂度为 $O(\log x)$。
算上线性筛就是 $O(n+\log x)$。

应用的话，我们可以利用这个算法时空复杂度 $O(n\log n)$ 地求解 Catalan 数模任意模数。

Solution

对于本题，可以栈的思想来证明本题为 Catalan 数。

Code

// Code by ajcxsu
// Problem: interesting series

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2e6+10;
int pri[N], lpri[N], p;
bool npri[N];
int cnt[N];

void add(int x, int d) {
    while(x!=1) {
        cnt[lpri[x]]+=d;
        x/=lpri[x];
    }
}

int main() {
    ios::sync_with_stdio(false);
    npri[0]=npri[1]=1;
    for(int i=2;i<N;i++) {
        if(!npri[i]) pri[p++]=i, lpri[i]=i;
        for(int j=0;j<p && i*pri[j]<N;j++) {
            npri[i*pri[j]]=1, lpri[i*pri[j]]=pri[j];
            if(i%pri[j]==0) break;
        }
    }
    ll n, p, ans=1;
    cin>>n>>p;
    for(int i=1;i<=n+1;i++) add(i, -1);
    for(int i=n+1;i<=2*n;i++) add(i, 1);
    for(int i=2;i<N;i++)
        while(cnt[i]) cnt[i]--, ans=(ans*i)%p;
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/prime_number.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆