首页 > 代码库 > bzoj 1005 HNOI2008 明明的烦恼

bzoj 1005 HNOI2008 明明的烦恼

    这题做的我欲哭无泪啊……

    我已经没心情多说啥了……

    高精度T啊!我太弱啊!改了一天啊!还不如滚粗啊!

    想好式子在写啊!

    能用高精度乘单精度就不要用高精度乘高精度啊!

    能用高精度除单精度就不要用高精度除高精度啊!

    T成翔啊!

    简单的组合计数问题啊!

    题解在这里=_= : http://www.cnblogs.com/zhj5chengfeng/archive/2013/08/23/3278557.html

    上代码:

#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#define N 1100using namespace std; class bignum{    public:        int l;        int num[N*3];        bignum(int nownum)        {            memset(num, 0, sizeof(num)); l = 0;            if (nownum == 0) l = 1;            else while (nownum)            {                num[++l] = nownum % 10;                nownum /= 10;            }        }        void jia(int y);        void chu(int y);        void cheng(int y);        void print();};int n, d[N], sum = 0; void bignum::jia (int y){    num[1] += y; int d = num[1] / 10; int i = 1;    while (d)    {        num[++i] = d;        d = num[i] / 10;        num[i] %= 10;    }    if (i > l) l = i;} void bignum::cheng (int y){    for (int i = 1; i <= l; ++i)        num[i] = num[i] * y;    int d = 0;    for (int i = 1; i <= l; ++i)    {        num[i] += d;        d = num[i] / 10;        num[i] %= 10;    }    while (d)    {        num[++l] = d;        d = num[l] / 10;        num[l] %= 10;    }    while (l > 1 && num[l] == 0) l--;} void bignum::chu (int y){    int yu = 0;    for (int i = l; i >= 1; --i)    {        yu = yu*10 + num[i];        num[i] = yu / y;        yu %= y;    }    while (l > 1 && num[l] == 0) l --;} void bignum::print(){    int d = 0;    for (int i = 1; i <= l; ++i)    {        num[i] += d;        d = num[i] / 10;        num[i] %= 10;    }    while (d) { num[++l] += d; d = num[l] / 10; num[l] %= 10; }    for (int i = l; i >= 1; --i) printf("%d", num[i]);    printf("\n"); return;} int main(){    scanf("%d", &n); int fre = 0;    for (int i = 1; i <= n; ++i)    {        scanf("%d", &d[i]);        if (d[i] != -1) { fre++; sum += d[i]-1; }    }    if (sum > n-2)    {        printf("0\n");        return 0;    }    bignum ans = 1;    for (int i = n-1-sum; i <= n-2; ++i) ans.cheng(i);    for (int i = 1; i <= n-sum-2; ++i) ans.cheng(n-fre);    for (int i = 1; i <= n; ++i)        if (d[i] > 2)            for (int j = 2; j < d[i]; ++j) ans.chu(j);    ans.print();    return 0;}

 

bzoj 1005 HNOI2008 明明的烦恼