思路（转）
( 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 表示。
如果有这么一个序列 01011010010011 11.
当第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) 接下来的化简就不推了.
#include<stdio.h>
#include<string.h>
int a[101][101][101]={0};
int b[101][101]={0}; //b数组里面保存的是a数组里面的元素个数
void qiuhe(int x0,int y0,int x1,int y1,int n)//大数相加这种方法可以先学习下，否则看起来比较吃力
{
int i,j,k=0;
j=b[x0][y0];
if(j<b[x1][y1])
j=b[x1][y1];
for(i=0;i<j;i++)
{
a[x0][y0][i]+=a[x1][y1][i]*n+k;
k=a[x0][y0][i]/10000;//每个元素四位
a[x0][y0][i]%=10000;
}
if(k)
{
a[x0][y0][j]=k;
b[x0][y0]=j+1;
}
else
b[x0][y0]=j;
}
void jiecheng(int n)//求大数阶乘
{
int i,j,k=0;
for(i=0;i<b[n-1][0];i++)
{
a[n][0][i]=1;
a[n][0][i]=a[n-1][0][i]*n+k;
k=a[n][0][i]/10000;
a[n][0][i]=a[n][0][i]%10000;
}
if(k)
{
a[n][0][i]=k;
b[n][0]=i+1;
}
else
b[n][0]=b[n-1][0];
}
int main()
{
int T=0,i,j,m,n;
a[1][0][0]=1;b[1][0]=1;
for(i=2;i<=100;i++)
jiecheng(i);//当m=0时的排列数
for(i=1;i<=100;i++)
for(j=i;j<=100;j++)
{
qiuhe(j,i,j-1,i,j);
qiuhe(j,i,j,i-1,i);
}
while(scanf("%d%d",&m,&n)!=EOF&&(m||n))
{
T++;
printf("Test #%d:\n",T);
printf("%d",a[m][n][b[m][n]-1]);
for(i=b[m][n]-2;i>=0;i--)
printf("%4.4d",a[m][n][i]);
printf("\n");
}
return 0;
}```
在排序问题的解决中，如果加上了两种个体的数量限制，则需要使用这种方法，n和m的阶乘在必要时候可以省去，但是需要注意的是假如需要A在Ｂ前面且A的数量为n，B数量为m，必须满足的条件是n》=m，否则方法为0；且在种类内部无需排序的情况下，如果m==0，那么方法种类为1，需要排序，种类为n！。
另：公式需熟记
网友评论