卡特兰数 BZOJ3907 网格 NOIP2003 栈

卡特兰数

卡特兰数2

卡特兰数：主要是求排列组合问题

1：括号化矩阵连乘，问多少种方案

2：走方格，不能过对角线，问多少种方案

3：凸边型，划分成三角形

4：1到n的序列进栈，有多少种出栈方案

 

NOIP2003 栈 

//#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <algorithm>
#include <vector>
// #include<malloc.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define LL long long
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
// const double pi = acos(-1);
const LL MOD = 1e8;
const int N=1<<13;
// const LL p = 1e9+7;
// inline int r(){
//     int x=0,f=1;char ch=getchar();
//     while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
//     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
//     return x*f;
// }

int main() {
    int n;
    LL f[20]={0};
    scanf("%d",&n);
    f[0]=1;f[1]=1;
    for(int i=2;i<=n;i++)
       for(int j=0;j<i;j++)
          f[i]+=f[j]*f[i-j-1];
    printf("%I64d\n",f[n]);
    return 0;
}

 

BZOJ3907 网格

转载

/**************************************************************
    Problem: 3907
    User: Tunix
    Language: C++
    Result: Accepted
    Time:84 ms
    Memory:944 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
 
typedef long long LL;
 
const int N=10001;
const LL mod=100000000;
 
int tot=0,x[N],p[N],v[N]={0};
LL a[1000],b[1000];
 
LL pow(LL x,int p) {
    LL t=1;for (;p;p>>=1,x*=x) if (p&1) t*=x;return t;
}
 
void mul(LL a[],LL y) {
    LL x=0,&l=a[0];
    for (int i=1;i<=l;i++) {
        a[i]=a[i]*y+x;
        x=a[i]/mod;
        a[i]%=mod;
    }
    while (x) a[++l]=x%mod,x/=mod;
}
 
void dec(LL a[],LL b[]) {
    LL &l=a[0];
    for (int i=1;i<=l;i++) {
        if (a[i]<b[i]) a[i+1]--,a[i]+=mod;
        a[i]-=b[i];
    }
    while (!a[l]) l--;
}
 
void getc(LL a[],int n,int m) {
    memset(x,0,sizeof x);
    for (int i=2;i<=n;i++) x[i]++;
    for (int i=2;i<=m;i++) x[i]--;
    for (int i=2;i<=n-m;i++) x[i]--;
    for (int i=n;i>=2;i--)
    if (!v[i]) mul(a,pow(i,x[i]));
    else x[v[i]]+=x[i],x[i/v[i]]+=x[i];
}
 
void print(LL a[]) {
    int l=a[0];
    printf("%lld",a[l]);
    for (int i=l-1;i>=1;i--) printf("%08lld",a[i]);
    printf("\n");
}
 
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=2;i<=n+m;i++) {
        if (!v[i]) p[++tot]=i;
        for (int j=1,k;j<=tot,(k=p[j]*i)<=n+m;j++) {
            v[k]=p[j];
            if (i%p[j]==0) break;
        }
    }
    a[0]=a[1]=b[0]=b[1]=1;
    getc(a,n+m,n);
    getc(b,n+m,n+1);
    dec(a,b);
    print(a);
    return 0;
}