博客

n个数，只能用<或者=连接，共有多少种方案。

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;
            }
            else if(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");
    }
    return 0;
}