题意：给n个字母，中间的符号可以为=或者<，问有多少种排列顺序，注意A=B和B=A是一样的
例如n=3
1) A=B=C
2) A=B<C
3) A<B=C
4) A<B<C
5) A<C<B
6) A=C<B
7) B<A=C
8) B<A<C
9) B<C<A
10) B=C<A
11) C<A=B
12) C<A<B
13) C<B<A
看网上的，
F[i][j]=(F[i-1][j]+F[i-1][j-1])*j
F[i][j]代表i个数，有j个不同值的情况。比如A<B=C<D,j=3.
数字比较大所以是大整数
#include <stdio.h>
#include <string.h>
const int MAX =505;
struct BigNum
{
int num[MAX];
int len;
} a[51][51];
BigNum Add(BigNum &a,BigNum &b)
{
BigNum c;
int i, len;
len = (a.len > b.len) ? a.len : b.len;
memset(c.num,0, sizeof(c.num));
for(i =0; i < len; i++)
{
c.num[i] += (a.num[i]+b.num[i]);
if(c.num[i] >=10)
{
c.num[i+1]++;
c.num[i] -=10;
}
}
if(c.num[len]) len++;
c.len = len;
return c;
}
BigNum Mul1(BigNum &a,int &b)
{
BigNum c;
int i, len;
len = a.len;
memset(c.num,0, sizeof(c.num));
//乘以0，直接返回0
if(b ==0)
{
c.len =1;
return c;
}
for(i =0; i < len; i++)
{
c.num[i] += (a.num[i]*b);
if(c.num[i] >=10)
{
c.num[i+1] = c.num[i]/10;
c.num[i] %=10;
}
}
while(c.num[len] >0)
{
c.num[len+1] = c.num[len]/10;
c.num[len++] %=10;
}
c.len = len;
return c;
}
void init()
{
int i,j;
for(i=0; i<=50; i++)
for(j=0; j<=50; j++)
if(i<j||j==0)
{
a[i][j].num[0]=0;
a[i][j].len=1;
}
elseif(j==1)
{
a[i][j].num[0]=1;
a[i][j].len=1;
}
else
{
a[i][j]=Add(a[i-1][j],a[i-1][j-1]);
a[i][j]=Mul1(a[i][j],j);
}
}
int main()
{
BigNum sum;
int i,p,n;
init();
scanf("%d",&p);
while(p--)
{
for(i=0;i<MAX;i++)
sum.num[i]=0;
sum.len=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
sum=Add(sum,a[n][i]);
for(i=sum.len-1;i>=0;i--)
printf("%d",sum.num[i]);
printf("\n");
}
return0;
}
/*************************
eleven，甚思，勿念，来世再见
你陪了我一年，没想到一年过得这么快