栈——火车进出栈问题（卡特兰数，组合计数+高精度乘法+筛质数+求n的阶乘里的质因数次数（模板））

传送门：130. 火车进出栈问题 - AcWing题库

思路：每一种可能都是进栈n次，以及出栈n次而来的，一共会有2*n次进出栈操作，进栈看'+',出栈看做‘-’，每一个合法序列都一定是有n个‘+’以及n个‘-’构成。

假设合法一个序列是4321，对应的就是++++----这样的字符串。

一个非法的字符串是----++++，这个是不存在的，没有对应的序列。

看一个+-序列是否和法看前i个字符中-的数量是否大于+的数量，将其转化到坐标轴上，+看成向右，-看成向上。

图中红色的路线就是一个合法路线——++--+++---

图中黑色的路线就是一个非法路线——++--+--++-，所有的路线终点都是（n,n）

其中所有的非法路线都一定会在某一时刻触碰到y=x+1的直线,而将触碰到y=x+1之后的路线与y=x+1对称画出来就是图中 1 的位置的路线，所以所有非法路径的数量就是所有从（0,0）到

（n-1,n+1）的路径的数量。

反着思考，将所有（0,0）到（n-1，n+1）的路径在第一次碰到y=x+1后面的路径沿着y=x+1对称折过来都可以对应一个（0,0）到(n,n)的非法路径。                                                                                                图中合法路径数的计算式：C(2*n,n)-C(2*n,n-1) =C(2*n,n)/(n+1)          在计算合法的的括号序列是也是一样的式子。

C(2*n,n)/(n+1)=(2*n)!/(n!*n!*(n+1));

用分解质因数来求

每一个数都可以分解成一些质因数的乘积

n！中的质因数p的个数= ⌊n/p⌋+ ⌊n/(p^2)⌋+ ⌊n/(p^3)⌋+...

压4位的正确代码：

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1200010;
int n;
int p[N];//记录一个质数
bool st[N];//标记质数
int cnt[N];//记录该质数要最后乘几次
int u;//记录范围内质数的个数
 
void get_p(int n)//埃筛法筛质数，标记合数
{
    for(int i=2;i<=n;i++)
        if(!st[i])
    {
        p[u++]=i;
        for(int j=i+i;j<=n;j+=i)
            st[j]=true;
    }
}
 
int get(int n,int p)//获取n的阶乘中p的次数
{
    int s=0;
    while(n)
    {
        s+=n/p;
        n/=p;
    }
    return s;
}
void mul(vector<int>&a,int b)//高精乘法
{
    int t=0;
    for(int i=0;isize();i++)
    {
        a[i]=a[i]*b+t;
        t=a[i]/10000;
        a[i]%=10000;
    }
    while(t)
    {
        a.push_back(t%10000);
        t/=10000;
    }
}
void output(vector<int>&s)
{
    cout<back();
    for(int i=s.size()-2;i>=0;i--)
        printf("%04d",s[i]);
    cout<
}
int main()
{
    int n;
    cin>>n;
    get_p(2*n);
 
    for(int i=0;i
    {
        int pp=p[i];
        cnt[pp]=get(2*n,pp)-get(n,pp)*2;//求质数p[i]的次数
    }
 
    int k=n+1;
    for(int i=0;i//因为分母中还有个（n+1）所以也要做一次筛，减少质因数次数
    {
        int pp=p[i],s=0;
        while(k%pp==0)
        {
            s++;
            k/=pp;
        }
        cnt[pp]-=s;
    }
    vector<int>res;
    res.push_back(1);
    
    for(int i=2;i<=2*n;i++)
    for(int j=0;j
        mul(res,i);           //质因数相乘
 
    output(res);
 
    return 0;
}

以下都是超时代码 

vector不压位代码：

#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n;
void mul(vector<int>&a,int b)
{
    int t=0;
    for(int i=0;isize();i++)
    {
        a[i]=a[i]*b+t;
        t=a[i]/10;
        a[i]%=10;
    }
    while(t)
    {
        a.push_back(t%10);
        t/=10;
    }
}
void div(vector<int>&a,int b)
{
    int t=0;
    for(int i=a.size()-1;i>=0;i--)
    {
        a[i]+=t*10;
        t=a[i]%b;
        a[i]/=b;
    }
    while(a.back()==0) a.pop_back();
}
int main()
{
    int n;
    cin>>n;
    vector<int>res;
    res.push_back(1);
    for(int i=2*n,j=1;j<=n;i--,j++)
    {
        mul(res,i);
        div(res,j);
    }
    div(res,n+1);
 
    for(int i=res.size()-1;i>=0;i--)
        printf("%d",res[i]);
    cout<
    return 0;
}

vector压位代码：

#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n;
void mul(vector<int>&a,int b)
{
    int t=0;
    for(int i=0;isize();i++)
    {
        a[i]=a[i]*b+t;
        t=a[i]/10000;
        a[i]%=10000;
    }
    while(t)
    {
        a.emplace_back(t%10000);
        t/=10000;
    }
}
void div(vector<int>&a,int b)
{
    int t=0;
    for(int i=a.size()-1;i>=0;i--)
    {
        a[i]+=t*10000;
        t=a[i]%b;
        a[i]/=b;
    }
    while(a.back()==0) a.pop_back();
}
int main()
{
    int n;
    scanf("%d",&n);
    vector<int>res;
    res.emplace_back(1);
    for(int i=2*n,j=1;j<=n;i--,j++)
    {
        mul(res,i);
        div(res,j);
    }
    div(res,n+1);
 
    printf("%d",res.back());
    for(int i=res.size()-2;i>=0;i--)
        printf("%04d",res[i]);
    printf("\n");
    return 0;
}

数组模拟vector开longlong：

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int n,tt;
ll res[6000010];
void mul(int b)
{
    ll t=0;
    for(int i=0;i<=tt;i++)
    {
        res[i]=res[i]*b+t;
        t=res[i]/1000000000;
        res[i]%=1000000000;
    }
    while(t)
    {
        res[++tt]=t%1000000000;
        t/=1000000000;
    }
}
void div(int b)
{
    ll t=0;
    for(int i=tt;i>=0;i--)
    {
        res[i]+=t*1000000000;
        t=res[i]%b;
        res[i]/=b;
    }
    while(!res[tt]) tt--;
}
int main()
{
    int n;
    scanf("%d",&n);
    tt=0;
    res[0]=1;
    for(int i=2*n,j=1;j<=n;i--,j++)
    {
        mul(i);
        div(j);
    }
    div(n+1);
    printf("%lld",res[tt]);
    for(int i=tt-1;i>=0;i--)
        printf("%09lld",res[i]);
    printf("\n");
    return 0;
}