LP3200 [HNOI2009] 有趣的数列 [线性筛素数/分解小数质因数]

Author Avatar
ajcxsu 2018年06月30日
  • 90 次阅读

填个坑....

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://acxblog.site/archives/prime_number.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。