卡特兰数的应用~~~ ^_^
1133 公式推导如下 :
//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
( C(m + n, n) - C(m + n, m + 1 ) ) * m ! * n ! 化简即 (m + n) ! * (m - n + 1 ) / (m + 1 )
推导过程如下 :
m个人拿50，n个人拿100
1 : 所以如果 n > m，那么排序方法数为 0 这一点很容易想清楚
2 : 现在我们假设 拿50的人用 ‘ 0 ’表示， 拿100的人用 1 表示。
如果有这么一个序列 0101101001001111 .
当第K个位置出现1的个数多余0的个数时就是一个不合法序列了
假设m = 4 n = 3的一个序列是： 0110100 显然，它不合法， 现在我们把它稍微变化一下：
把第二个1（这个1前面的都是合法的）后面的所有位0变成1，1变成0
就得到 0111011 这个序列1的数量多于0的数量， 显然不合法， 但现在的关键不是看这个序列是不是合法的
关键是：它和我们的不合法序列 0110100 成一一对应的关系
也就是说任意一个不合法序列(m个0，n个1)， 都可以由另外一个序列(n - 1个0和m + 1个1)得到
另外我们知道，一个序列要么是合法的，要么是不合法的
所以，合法序列数量 = 序列总数量 - 不合法序列的总量
序列总数可以这样计算m + n 个位置中， 选择 n 个位置出来填上 1 ， 所以是 C(m + n, n)
不合法序列的数量就是： m + n 个位置中， 选择 m + 1 个位置出来填上 1 所以是 C(m + n, m + 1 )
然后每个人都是不一样的，所以需要全排列 m ! * n !
所以最后的公式为 : ( C(m+n, n) - C(m+n, m+1) ) * m! * n! 化简即 (m+n)! * (m-n+1) / (m+1)
推广:
如果原来有p张50元的话,那么不合法的序列的数量应该是:任意一个不合法序列(m个0，n个1)，
都可以由另外一个序列(n - 1个0和m + 1 + p个1)得到,所以是m + n 个位置中， 选择 m + 1 + p 个位置
出来填上 1 所以是 C(m + n, m + 1 + p) 接下来的化简就不推了.
Code： #include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include<stdio.h>
#include<string.h>
using namespace std;
const int Base=10000;
//万进制 int 最大,如果只用 +,-,可加大Base=1000000000
int ONE[]={1,1}; //大整数 1
int ZERO[]={1,0}; //大整数 0
//大整数比较大小
int comp(int *a, int *b) {
int i;
if (a[0] > b[0])return 1;
if (a[0] < b[0])return -1;
for (i = a[0]; i >= 1; i--) {
if (a[i] > b[i])return 1;
if (a[i] < b[i])return -1;
}
return 0;
}
int comp(int *a, int *b,int t) {
int i,j=1;
for (i = b[0]; i >= 1; i--,j++) {
if (a[t] > b[i])return j;
if (a[t] < b[i])return -1;
t--;
}
return 0;
}
void PN(int *a){
int i;//输出 "%04d" 10000进制
printf("%d", a[a[0]]);
for(i=a[0]-1;i>=1;i--)printf("%04d", a[i]);printf("\n");
}
void copy(int *a, int *b)
{ int i; //a=b
for (i = 0;i<= b[0]; ++i)a[i] = b[i];
}
//大整数a乘常数 b b<Base, d=a*b
void mult(int *a,int b,int *d)
{ int w, i,p;
if(b==1){copy(d,a);return;}
if((b==0)||(a[0]==1&&a[1]==0)){d[0]=1;d[1]=0;return;}
w = a[0];
p = 0; //
for (i = 1; i <= w; i++)
{ d[i] = a[i] * b + p;
if (d[i] >= Base)
{ p = d[i] / Base; d[i] %= Base;}else p=0;
}
if (p) {w++;d[w] = p;}
d[0] = w;
}
// c=a/b k=a%b
int Div(int *a,int b,int *c)
{int i,j,s,t;
int k=0,q;
// long long k=0,q; Base>=100000
if(comp(a,ZERO)==0){copy(c,ZERO);return 0;}
for(i=a[0];i>=1;i--)
{q=k*Base+a[i];
c[i]=q/b;k=q%b;
}
if(c[a[0]]==0)
{ c[0]=a[0]-1;
}else c[0]=a[0];
return k;
}
int a[10000],b[10000],c[10000];
int main(){
int ca=1;
int n,m;
while(scanf("%d%d",&m,&n)!=EOF){
if(m+n==0) break;
printf("Test #%d:\n",ca++);
a[0]=1,a[1]=1;
if(n>m){
printf("0\n");
continue;
}
for(int i=2;i<=m+n;i++){
mult(a,i,b);
copy(a,b);
}
mult(a,m-n+1,b);
copy(a,b);
Div(a,m+1,c);
PN(c);
}
}