题目：bzoj3907：https://www.lydsy.com/JudgeOnline/problem.php?id=3907
bzoj2822：https://www.lydsy.com/JudgeOnline/problem.php?id=2822
bzoj3907：
从网格图的角度很好想啊，就是像定义一样，一下子就出来了 ans = C(n+m,n) - C(n+m,m-1)；
那么从01串的角度呢？这个是0和1的个数不同的问题呢...
看到这篇博客：https://blog.csdn.net/u014097230/article/details/44244793
里面有很多很好的小例子！其中的 hdu 1133，不正可以转化成这道题吗！
于是就解决了，得到的答案和上面那种方法得到的一样：ans = C(n+m,n) - C(n+m,m-1)；
然而难道是卡特兰数的题都太容易写了，所以非得来个高精度？！一时间不想做了...
直到看到了这篇博客：https://www.cnblogs.com/Tunix/p/4354348.html
怎么会有这么优美的高精度求组合数写法！！！顿时有了信心，马上抄了一遍成功写好了！
我会牢牢记住这篇美丽的高精度的(话说好像还是第一次写高精度求组合数啊)。
bzoj2822：就是求卡特兰数第 n 项，因为正好符合了那个递推式；
也要高精度，就用同一个板子A了(令 m = n 就好啦)。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int const maxn=,mod=1e8;
int n,m,pri[maxn],mn[maxn],cnt,p[maxn];
ll a[],b[];
void init()
{
mn[]=;
for(int i=;i<=n+m;i++)
{
if(!mn[i])pri[++cnt]=i,mn[i]=i;
for(int j=;j<=cnt&&i*pri[j]<=n+m;j++)
{
mn[i*pri[j]]=pri[j];
if(i%pri[j]==)break;
}
}
}
ll pw(int a,int b)
{
ll ret=;
for(;b;b>>=,a*=a)
if(b&)ret*=a;
return ret;
}
void mul(ll a[],ll k)
{
ll x=;
for(int i=;i<=a[];i++)
{
a[i]=a[i]*k+x;
x=a[i]/mod;
a[i]%=mod;
}
while(x)a[++a[]]+=x%mod,x/=mod;
}
void getc(ll a[],int n,int m)
{
memset(p,,sizeof p);
for(int i=;i<=n;i++)p[i]++;
for(int i=;i<=m;i++)p[i]--;
for(int i=;i<=n-m;i++)p[i]--;
for(int i=n;i>=;i--)
{
if(mn[i]==i) mul(a,pw(i,p[i]));
else p[mn[i]]+=p[i],p[i/mn[i]]+=p[i];//转化到质因子上！太妙了！
}
}
void dec(ll a[],ll b[])
{
for(int i=;i<=a[];i++)
{
if(a[i]<b[i])a[i]+=mod,a[i+]--;
a[i]-=b[i];
}
while(a[]&&!a[a[]])a[]--;
}
void print(ll a[])
{
printf("%lld",a[a[]]);
for(int i=a[]-;i;i--)
printf("%08lld",a[i]);
printf("\n");
}
int main()
{
scanf("%d%d",&n,&m);
init();
a[]=a[]=b[]=b[]=;
getc(a,n+m,n);
getc(b,n+m,m-);
dec(a,b);
print(a);
return ;
}