출입고 서열 문제(카틀란수 + 조합수의 질인수 분해 구법)

제목: 1 N 1 ~ N 1 N을 지정합니다. 이 N N의 정수와 무한대 창고를 지정합니다. 모든 수는 창고에 들어가서 한 번씩 창고를 나가야 합니다.창고에 들어오는 순서가 1, 2,...  이면N1,2,\cdots,N1,2,,,,N,그러면 가능한 출고 서열은 몇 가지가 있나요?문제: 먼저 c o d e 검색을 고려합니다. code: code:

#include
using namespace std;
int n;
vector<int>state1;
stack<int>state2;
int state3=1,cnt=20;
void dfs()
{
    if(!cnt)return ;
    if(state1.size()==n){
        cnt--;
        for(auto &p:state1)cout<<p;
        cout<<endl;
        return ;
    }
    if(state2.size()){
        state1.push_back(state2.top());
        state2.pop();
        dfs();
        state2.push(state1.back());
        state1.pop_back();
    }
    if(state3<=n){
        state2.push(state3);
        state3++;
        dfs();
        state3--;
        state2.pop();
    }
}
int main()
{
    cin>>n;
    dfs();
    return 0;
}

그러나 데이터 범위가 백만 단계라면 검색은 틀림없이 안 될 것이다. 출대 서열을 하나의 ′+-3′'+-'′+-3′ 서열로 바꿀 수 있고, 입고는 ′+′'+'′+′+′로 바꿀 수 있으며, 출고는 ′-3′'-'-′-′로 바꿀 수 있다. 모든 합리적인 ′+-3′'+-'+-'′+-3′ 서열을 구할 수 있다면, 그 다음에 서열을 그림의 경로로 바꿀 수 있으며, 모든 서열은 (n, n)(n, n, n),불합리한 서열은 적당한 변환을 통해 (n: 1, n + 1)(n-1, n+1)(n: 1, n+1)(n: 1, n+1)까지 갈 수 있기 때문에 카틀란수는 C(n, 2는 n) - C(n: 1, 2는 n) C(n, 2*n) - C(n, 2*n) C(n, 1,2*n) C(n, 2는 n) - C(n, 2는 n) - C(n, 2는 n) - C(n, 2는 n) - C(n, 1,2는 n) - C(n, 1,1,2는 1, 2는 1, 2는 n) - C(n-n, 1,1, 2는 n, n, n, n은 n, n은 n, n은 n, n, n은 (n, n, n, n, n, n, n, n, n, n, n, N+1} N+1C(n,2∗n), 여기까지는 끝났지만 이 조합수의 알고리즘은 큰 구덩이,질인수분해법을 사용해야만 T, 질인수분해법을 초래하지 않는다. 예를 들어 공식 C(m, n)=n을 보면 된다!m ! ( n − m ) ! C(m,n)=\frac{n!}{m!(n-m)!} C(m,n)=m!(n−m)!n!위아래 도질인수를 분해한 다음에 남은 질인수를 곱하고 싶은 것이 답이다. 이렇게 하면 곱하면서 나누는 것보다 많은 시간을 절약할 수 있고 곱하면서 나누는 높은 정밀도는 마지막에 크게 올라간다. 이런 숫자는 순서대로 늘어날 뿐이다.하나의 곱셈의 질인수 분해도 공식이 있다. 예를 들어 n!n! n!중 2의 幂次는 한 사람이 계산하는 것이 아니다. 공식은 n2+n2+n2+n23+...\rac{n} {2} +\rac{n} {2^2} +\rac{n} {2^3} +\cdots2n+22n+23n+...c o d e : code: code:

#include
#define ll long long
using namespace std;
const int N=120000+5;
int n,primes[N],cnt,st[N],powers[N];
void get_primes(int n)
{
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            for(int j=i+i;j<=n;j+=i){
                st[j]=1;
            }
        }
    }
}
int get(int n,int p)
{
    int s=0;
    while(n){
        s+=n/p;
        n/=p;
    }
    return s;
}
void multi(vector<ll> &a,int b)
{
    ll t=0;
    for(int i=0;i<a.size();i++){
        a[i]=a[i]*b+t;
        t=a[i]/100000000;
        a[i]=a[i]%100000000;
    }
    while(t){
        a.push_back(t%100000000);
        t/=100000000;
    }
}
void out(vector<ll> &a)
{
    printf("%lld",a.back());
    for(int i=a.size()-2;i>=0;i--)printf("%08lld",a[i]);
    printf("
");
}
int main()
{
    int n;
    scanf("%d",&n);
    get_primes(n*2);
    for(int i=0;i<cnt;i++){
        int p=primes[i];
        powers[p]=get(2*n,p)-get(n,p)*2;
    }
    int k=n+1;
    for(int i=0;i<cnt&&primes[i]<=k;i++){
        while(k%primes[i]==0){
            k/=primes[i];
            powers[primes[i]]--;
        }
    }
    vector<ll>res;
    res.push_back(1);
    for(int i=0;i<cnt;i++){
        for(int j=0;j<powers[primes[i]];j++){
            multi(res,primes[i]);
        }
    }
    out(res);
    return 0;
}