カトラン数の性質を用い,高精度圧位,ふるい法による素数探しを行った.

1列の列車のn両の車両、順番に番号が1,2,3,...,nです.
各車両には2つの運動方式があり、入桟と出桟があり、n車両の出桟の可能な配列方式は何種類あるかを聞く.
入力フォーマットは、列車の車両数を表す整数nを入力します.
出力フォーマット出力整数sは、n両の車両スタックの可能な配列数を表す.
データ範囲1≦n≦60000入力サンプル:3出力サンプル:5
この問題の本質はカトラン数だ
カトラン数紹介(math 73参照)
ふるいほうそすう
最も重要なのは,組合せ数をどのように解くか,圧位思想,また組合せ数C(2 n)(n)という式を展開した後,連続した質量数を上下同時に除算する方法で,毎回長い数を1つの数で除去するのではなく,答えを少しずつ集め,運転時間を低減することである.

    #include
    #include
    #include
    using namespace std;
    const int N=120010;
    int powers[N];//       
    int primes[N],cnt;/   2~2*n    
    bool st[N];//            
    typedef long long ll;
    void get_primes(int n)//         
    {
        for(int i=2;i<=n;i++)
        if(!st[i])
        {
            primes[cnt++]=i;
            for(int j=i*2;j<=n;j+=i)
            st[j]=true;
        }
    }
    int get(int n,int p)//n          p
    {
        ll s=0;
        while(n)
        {
            s+=n/p;
            n/=p;
        }
        return s;
    }
    void multi(vector&a,int b)//       
    {
        int t=0;
        for(int i=0;i&a)//  
    {
        printf("%lld",a.back());
        for(int i=a.size()-2;i>=0;i--)
        printf("%08lld",a[i]);
        cout<>n;
        get_primes(n*2);
        for(int i=0;ires;
        res.push_back(1);
            for(int i=2;i<=n*2;i++)
               for(int j=0;j