1223 order count.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1223 Order Count
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
/*
动态规划DP
S[n]= Sum[F[n,i],{i,1,n}]
F[m,t]=(F[m-1,t-1]+F[m-1,t])*t
注意大数
*/

#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
#include <stdio.h>
using namespace std;

const int sizeMax=100;
const int divNum=10000;
const int divLen=4;

typedef struct
{
    int now;   //当前位置
    int base[sizeMax];
}BigNum;

int initBigNum(BigNum &num,char* snum)
{
    int len;
    num.now=0;
    memset(num.base,0,sizeof(num.base));
    len=strlen(snum);
    do
    {
        len-=divLen;
        if(len<0)
            len=0;
        num.base[num.now]=atoi(&snum[len]);
        snum[len]='\0';
        num.now++;
    }while(len>0);
    num.now--;
    return 1;
}

int initBigNum(BigNum &bnum,int num)
{
    int len,temp;
    bnum.now=0;
    memset(bnum.base,0,sizeof(bnum.base));
    do
    {
        temp=num%divNum;
        num/=divNum;
        bnum.base[bnum.now]=temp;
        bnum.now++;
    }while(num>0);
    bnum.now--;
    return 1;
}

int display(const BigNum &num)
{
    int i;

    //cout << num.base[num.now];
    printf("%d",num.base[num.now]);
    for(i = num.now-1 ; i >= 0 ; i--)
    {
        //cout.width(divLen);
        //cout.fill('0');
        //cout << num.base[i];
        printf("%04d",num.base[i]);
    }
    //cout << endl;
    printf("\n");
    return 1;
}

int whoBig(const BigNum &num1,const BigNum &num2)
{
    int ln;
    if(num1.now > num2.now) return 1;
    else
    if(num1.now == num2.now)
    {
        ln = num1.now;
        while(num1.base[ln] == num2.base[ln] && ln >= 0) ln--;

        if(ln >= 0 && num1.base[ln] > num2.base[ln]) return 1;
        else return -1;
    }
    else return -1;

    return 0;
}

int isNegtive(const BigNum &num)
{
    if(num.base[num.now]>0)
        return 0;
    else
        return 1;
}

int subMe(BigNum &num1,BigNum &num2)
{
    int i,j,biglen;
    BigNum *big,*small;
    BigNum temp;
    bool flag;
    temp.now=0;
    memset(temp.base,0,sizeof(temp.base));

    switch(whoBig(num1,num2))
    {
    case 1:
        big=&num1;
        small=&num2;
        flag=false;
        break;
    case -1:
        temp=num2;
        big=&temp;
        small=&num1;
        flag=true;
        break;
    case 0:
        num1.base[0]=0;
        num1.now=0;
        return 0;
    }

    biglen=big->now;
    for(i = 0 ; i <= biglen ; i++)
    {
        if(big->base[i] < small->base[i])
        {
            j = i + 1;
            while(big->base[j] == 0) j++;
            big->base[j--]--;
            while(j > i) big->base[j--] += divNum;
            big->base[i] = big->base[i] + divNum - small->base[i];
        }
        else big->base[i] -= small->base[i];
    }
    big->now = biglen;
    while(big->base[big->now] == 0 && big->now >0) big->now--;

    if(flag)
    {
        temp.base[temp.now]=-temp.base[temp.now];
        num1=temp;
    }
    return 1;
}

int plusMe(BigNum &num1,const BigNum &num2)
{
    int i,big;

    big = num2.now > num1.now ? num2.now : num1.now;
    for(i = 0 ; i <= big ; i++)
    {
        num1.base[i] = num1.base[i] + num2.base[i];
        if(num1.base[i] >= divNum)
        {
            num1.base[i + 1] +=num1.base[i]/divNum;
            num1.base[i] %=divNum;
        }
    }
    if(num1.base[big+1] != 0) num1.now = big + 1;
    else num1.now = big;

    return 1;
}

BigNum plus(const BigNum &num1,const BigNum &num2)
{
    int i,big;
    BigNum ans;

    big = num2.now > num1.now ? num2.now : num1.now;
    ans.now=0;
    memset(ans.base,0,sizeof(ans.base));
    for(i = 0 ; i <= big ; i++)
    {
        ans.base[i] += num1.base[i] + num2.base[i];
        if(ans.base[i] >= divNum)
        {
            ans.base[i + 1] =ans.base[i]/divNum;
            ans.base[i] %=divNum;
        }
    }
    if(ans.base[big+1] != 0) ans.now = big + 1;
    else ans.now = big;

    return ans;
}

BigNum  multiple(const BigNum &num1,const BigNum &num2)
{
    BigNum ret;
    int i,j,up;
    int temp,temp1;

    ret.now=0;
    memset(ret.base,0,sizeof(ret.base));
    for(i = 0 ; i <= num1.now ; i++)
    {
        up = 0;
        for(j = 0 ; j <= num2.now ; j++)
        {
            temp = num1.base[i] * num2.base[j] + ret.base[i + j] + up;
            if(temp >= divNum)
            {
                temp1 = temp - temp / divNum * divNum;
                up = temp / divNum;
                ret.base[i + j] = temp1;
            }
            else
            {
                up = 0;
                ret.base[i + j] = temp;
            }
        }
        if(up != 0)
            ret.base[i + j] = up;
    }
    ret.now = i + j;
    while(ret.base[ret.now] == 0 && ret.now > 0) ret.now--;

    return ret;
}

BigNum  multiple(const BigNum &num1,const int num2)
{
    BigNum ret;
    int i,up;
    int temp,temp1;

    up = 0;
    ret.now=0;
    memset(ret.base,0,sizeof(ret.base));
    for(i = 0 ; i <= num1.now ; i++)
    {
        temp = num1.base[i] * num2 + ret.base[i] + up;
        if(temp >= divNum)
        {
            temp1 = temp % divNum;
            up = temp / divNum;
            ret.base[i] = temp1;
        }
        else
        {
            up = 0;
            ret.base[i] = temp;
        }

    }
    if(up != 0)
        ret.base[i] = up;
    ret.now = i;
    while(ret.base[ret.now] == 0 && ret.now > 0) ret.now--;

    return ret;
}

const int PMAX=1000;
const int NMAX=50;

int main()
{
    int p,n,ca,cb,cc;
    BigNum frec[NMAX+1]={0},ans;
    while(scanf("%d",&p)==1)
    {
        for(ca=0;ca<p;ca++)
        {
            scanf("%d",&n);
            //frec[1].len=1;
            //memset(frec,0,sizeof(frec));
            initBigNum( frec[1],1 );
            for(cb=2;cb<=n;cb++)
            {
                frec[cb]=frec[cb-1];
                frec[cb]=multiple( frec[cb],cb );
                for(cc=cb-1;cc>=2;cc--)
                {
                    //frec[cc].Add(frec[cc-1]);
                    plusMe( frec[cc],frec[cc-1] );
                    //frec[cc]=frec[cc]*cc;
                    frec[cc]= multiple ( frec[cc],cc );
                }
            }

            initBigNum( ans,0 );
            for(cb=1;cb<=n;cb++)
                plusMe( ans,frec[cb] );

            display(ans);
        }//for
    }
    return 0;
}