高端洋气的大数模板

发布时间：2020-12-14 03:56:47 所属栏目：大数据来源：网络整理

导读：一般大数，常常是在JAVA里用bigInteger来写，但是在C++里也有大数的类，今天看长春赛结题报告的时候突然有看到，似乎很强大的样子。 HDU4762 Cut the Cake Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others) Total Subm

一般大数，常常是在JAVA里用bigInteger来写，但是在C++里也有大数的类，今天看长春赛结题报告的时候突然有看到，似乎很强大的样子。 HDU4762

Cut the Cake

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 640????Accepted Submission(s): 311

Problem Description

MMM got a big big big cake,and invited all her M friends to eat the cake together. Surprisingly one of her friends HZ took some (N) strawberries which MMM likes very much to decorate the cake (of course they also eat strawberries,not just for decoration). HZ is in charge of the decoration,and he thinks that it's not a big deal that he put the strawberries on the cake randomly one by one. After that,MMM would cut the cake into M pieces of sector with equal size and shape (the last one came to the party will have no cake to eat),and choose one piece first. MMM wants to know the probability that she can get all N strawberries,can you help her? As the cake is so big,all strawberries on it could be treat as points.

Input

First line is the integer T,which means there are T cases.
For each case,two integers M,N indicate the number of her friends and the number of strawberry.
(2 < M,N <= 20,T <= 400)

Output

As the probability could be very small,you should output the probability in the form of a fraction in lowest terms. For each case,output the probability in a single line. Please see the sample for more details.

Sample Input

Sample Output

Source

2013 ACM/ICPC Asia Regional Changchun Online

用这题Jacob的代码来记录下大数类模板

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <limits>
#include <cstdlib>
using namespace std;
const int MAXD = 500,DIG = 9,BASE = 1000000000;
const unsigned long long BOUND = numeric_limits <unsigned long long> :: max () - (unsigned long long) BASE * BASE;
class bignum
{
    private:
         int digits[MAXD];
         int D;
    public:
    friend ostream &operator<<(ostream &out,bignum &c);
    inline void trim()
    {
           while(D > 1 && digits[D-1] == 0 )
               D--;
    }
    inline void dealint(long long x)
    {
           memset(digits,sizeof(digits));
           D=0;
           do
           {
                digits[D++]=x%BASE;
                x/=BASE;
           }
           while(x>0);
    }

    inline void dealstr(char *s)
    {
          memset(digits,sizeof(digits));
          int len = strlen(s),first = (len + DIG -1)%DIG + 1;
          D = (len+DIG-1)/DIG;
          for(int i = 0; i < first; i++)
              digits[D-1] = digits[D-1]*10 + s[i] - '0';
          for(int i = first,d = D-2; i < len; i+=DIG,d--)
              for(int j = i; j < i+DIG; j++)
                  digits[d] = digits[d]*10 + s[j]-'0';
          trim();
    }

    inline char *print()
    {
          trim(); 
          char *cdigits = new char[DIG * D + 1]; 
          int pos = 0,d = digits[D-1]; 
          do
          {
                cdigits[pos++] = d % 10 + '0';
                d/=10;
          }
          while(d > 0); 
          reverse(cdigits,cdigits+pos); 
          for(int i = D - 2; i >= 0; i--,pos += DIG)
              for(int j = DIG-1,t = digits[i]; j >= 0; j--)
              {
                    cdigits[pos+j] = t%10 + '0';
                    t /= 10;
              } 
        cdigits[pos] = ''; 
        return cdigits;
    } 
    bignum()
    {
        dealint(0);
    } 
    bignum(long long x)
    {
        dealint(x);
    } 
    bignum(int x)
    {
        dealint(x);
    } 
    bignum(char *s)
    {
        dealstr(s);
    } 
    inline bool operator < (const bignum &o) const
    {
        if(D != o.D)
            return D < o.D;

        for(int i = D-1; i>=0; i--)
            if(digits[i] != o.digits[i])
                return digits[i] < o.digits[i];
        return false; //equal

    } 
    bool operator >  (const bignum & o)const
    {
        return o < *this;
    }
    bool operator <= (const bignum & o)const
    {
        return !(o < *this);
    }
    bool operator >= (const bignum & o)const
    {
        return !(*this < o);
    }
    bool operator != (const bignum & o)const
    {
        return o < *this || *this < o;
    }
    bool operator == (const bignum & o)const
    {
        return !(o < *this) && !(*this < o);
    }
 
    bignum &operator++()
    {
        *this = *this  + 1;
        return *this;
    }
 
    bignum operator ++(int)
    {
        bignum old = *this;
        ++(*this);
        return old;
    } 
    inline bignum operator << (int p) const
    {
        bignum temp;
        temp.D = D + p;

        for (int i = 0; i < D; i++)
            temp.digits [i + p] = digits [i];

        for (int i = 0; i < p; i++)
            temp.digits [i] = 0;

        return temp;
    }

    inline bignum operator >> (int p) const
    {
        bignum temp;
        temp.D = D - p;

        for (int i = 0; i < D - p; i++)
            temp.digits [i] = digits [i + p];

        for (int i = D - p; i < D; i++)
            temp.digits [i] = 0;

        return temp;
    }
 
    bignum &operator += (const bignum &b)
    {
        *this = *this + b;
        return *this;
    }

    bignum &operator -= (const bignum &b)
    {
        *this = *this - b;
        return *this;
    }

    bignum &operator *= (const bignum &b)
    {
        *this = *this * b;
        return *this;
    }

    bignum &operator /= (const bignum &b)
    {
        *this = *this / b;
        return *this;
    }

    bignum &operator %= (const bignum &b)
    {
        *this = *this % b;
        return *this;
    }

    inline bignum operator + (const bignum &o) const
    {
        bignum sum = o;
        int carry = 0;

        for (sum.D = 0; sum.D < D || carry > 0; sum.D++)
        {
            sum.digits [sum.D] += (sum.D < D ? digits [sum.D] : 0) + carry;

            if (sum.digits [sum.D] >= BASE)
            {
                sum.digits [sum.D] -= BASE;
                carry = 1;
            }
            else
                carry = 0;
        }

        sum.D = max (sum.D,o.D);
        sum.trim ();
        return sum;
    }
    inline bignum operator - (const bignum &o) const
    {
        bignum diff = *this;

        for (int i = 0,carry = 0; i < o.D || carry > 0; i++)
        {
            diff.digits [i] -= (i < o.D ? o.digits [i] : 0) + carry;

            if (diff.digits [i] < 0)
            {
                diff.digits [i] += BASE;
                carry = 1;
            }
            else
                carry = 0;
        }

        diff.trim ();
        return diff;
    }
    inline bignum operator * (const bignum &o) const
    {
        bignum prod = 0;
        unsigned long long sum = 0,carry = 0;

        for (prod.D = 0; prod.D < D + o.D - 1 || carry > 0; prod.D++)
        {
            sum = carry % BASE;
            carry /= BASE;

            for (int j = max (prod.D - o.D + 1,0); j <= min (D - 1,prod.D); j++)
            {
                sum += (unsigned long long) digits [j] * o.digits [prod.D - j];

                if (sum >= BOUND)
                {
                    carry += sum / BASE;
                    sum %= BASE;
                }
            }

            carry += sum / BASE;
            prod.digits [prod.D] = sum % BASE;
        }

        prod.trim ();
        return prod;
    }
    inline bignum range (int a,int b) const
    {
        bignum temp = 0;
        temp.D = b - a;

        for (int i = 0; i < temp.D; i++)
            temp.digits [i] = digits [i + a];

        return temp;
    }


    inline double double_div (const bignum &o) const
    {
        double val = 0,oval = 0;
        int num = 0,onum = 0;

        for (int i = D - 1; i >= max (D - 3,0); i--,num++)
            val = val * BASE + digits [i];

        for (int i = o.D - 1; i >= max (o.D - 3,onum++)
            oval = oval * BASE + o.digits [i];

        return val / oval * (D - num > o.D - onum ? BASE : 1);
    }

    inline pair <bignum,bignum> divmod (const bignum &o) const
    {
        bignum quot = 0,rem = *this,temp;

        for (int i = D - o.D; i >= 0; i--)
        {
            temp = rem.range (i,rem.D);
            int div = (int) temp.double_div (o);
            bignum mult = o * div;

            while (div > 0 && temp < mult)
            {
                mult = mult - o;
                div--;
            }

            while (div + 1 < BASE && !(temp < mult + o))
            {
                mult = mult + o;
                div++;
            }

            rem = rem - (o * div << i);

            if (div > 0)
            {
                quot.digits [i] = div;
                quot.D = max (quot.D,i + 1);
            }
        }

        quot.trim ();
        rem.trim ();
        return make_pair (quot,rem);
    }

    inline bignum operator / (const bignum &o) const
    {
        return divmod (o).first;
    }

    inline bignum operator % (const bignum &o) const
    {
        return divmod (o).second;
    }


    inline bignum power (int exp) const
    {
        bignum p = 1,temp = *this;

        while (exp > 0)
        {
            if (exp & 1) p = p * temp;
            if (exp > 1) temp = temp * temp;
            exp >>= 1;
        }

        return p;
    }

    inline bignum factorial() const
    {
        bignum ans = 1,num = *this;

        if (num == 0 || num == 1)
            return ans;
        while (!(num < 0 || num == 0))
        {
            ans = ans * num;
            num = num - 1;
        }
        return ans;
    }
};

ostream &operator<<(ostream &out,bignum &c)
{
    out<<c.print();
    return out;
}

istream &operator >> (istream &in,bignum &c)
{
    char s[500];
    in>>s;
    c = s;
    return in;
}
bignum gcd(bignum a,bignum b)
{
    return b==0?a:gcd(b,a%b);
} 
bignum N,M,x;
int main()
{
    int cases,i,a,b; 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cin>>cases;
    while (cases--)
    {
            cin>>b>>a;
            M=1;
            for (i=1;i<=a-1;i++) M=M*b;
            N=a;
            x=gcd(N,M);
            N=N/x;
            M=M/x;
            cout<<N<<"/"<<M<<endl;            
    }
    return 0;
}

再用一个同是长春赛区的Kuangbin的解题报告 HDU4759

Poker Shuffle

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 370????Accepted Submission(s): 114

Problem Description

Jason is not only an ACMer,but also a poker nerd. He is able to do a perfect shuffle. In a perfect shuffle,the deck containing K cards,where K is an even number,is split into equal halves of K/2 cards which are then pushed together in a certain way so as to make them perfectly interweave. Suppose the order of the cards is (1,2,3,4,…,K-3,K-2,K-1,K). After a perfect shuffle,the order of the cards will be (1,K) or (2,K,1,K-1).?
Suppose K=2^N and the order of the cards is (1,K) in the beginning,is it possible that the A-th card is X and the B-th card is Y after several perfect shuffles?

Input

Input to this problem will begin with a line containing a single integer T indicating the number of datasets.
Each case contains five integer,N,A,X,B,Y. 1 <= N <= 1000,1 <= A,Y <= 2^N.

Output

For each input case,output “Yes” if it is possible that the A-th card is X and the B-th card is Y after several perfect shuffles,otherwise “No”.

3 1 1 1 2 2 2 1 2 4 3 2 1 1 4 2

Case 1: Yes Case 2: Yes Case 3: No

2013 ACM/ICPC Asia Regional Changchun Online

#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

/*
 * 完全大数模板
 * 输出cin>>a
 * 输出a.print();
 * 注意这个输入不能自动去掉前导0的，可以先读入到char数组，去掉前导0，再用构造函数。
 */
#define MAXN 9999
#define MAXSIZE 1010
#define DLEN 4

class BigNum
{
public:
    int a[500];  //可以控制大数的位数
    int len;
public:
    BigNum(){len=1;memset(a,sizeof(a));}  //构造函数
    BigNum(const int);     //将一个int类型的变量转化成大数
    BigNum(const char*);   //将一个字符串类型的变量转化为大数
    BigNum(const BigNum &); //拷贝构造函数
    BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算
    friend istream& operator>>(istream&,BigNum&); //重载输入运算符
    friend ostream& operator<<(ostream&,BigNum&); //重载输出运算符

    BigNum operator+(const BigNum &)const;  //重载加法运算符，两个大数之间的相加运算
    BigNum operator-(const BigNum &)const;  //重载减法运算符，两个大数之间的相减运算
    BigNum operator*(const BigNum &)const;  //重载乘法运算符，两个大数之间的相乘运算
    BigNum operator/(const int &)const;     //重载除法运算符，大数对一个整数进行相除运算

    BigNum operator^(const int &)const;     //大数的n次方运算
    int operator%(const int &)const;        //大数对一个int类型的变量进行取模运算
    bool operator>(const BigNum &T)const;   //大数和另一个大数的大小比较
    bool operator>(const int &t)const;      //大数和一个int类型的变量的大小比较

    void print();        //输出大数
};
BigNum::BigNum(const int b)   //将一个int类型的变量转化为大数
{
    int c,d=b;
    len=0;
    memset(a,sizeof(a));
    while(d>MAXN)
    {
        c=d-(d/(MAXN+1))*(MAXN+1);
        d=d/(MAXN+1);
        a[len++]=c;
    }
    a[len++]=d;
}
BigNum::BigNum(const char *s)  //将一个字符串类型的变量转化为大数
{
    int t,k,index,L,i;
    memset(a,sizeof(a));
    L=strlen(s);
    len=L/DLEN;
    if(L%DLEN)len++;
    index=0;
    for(i=L-1;i>=0;i-=DLEN)
    {
        t=0;
        k=i-DLEN+1;
        if(k<0)k=0;
        for(int j=k;j<=i;j++)
            t=t*10+s[j]-'0';
        a[index++]=t;
    }
}
BigNum::BigNum(const BigNum &T):len(T.len)  //拷贝构造函数
{
    int i;
    memset(a,sizeof(a));
    for(i=0;i<len;i++)
        a[i]=T.a[i];
}
BigNum & BigNum::operator=(const BigNum &n)  //重载赋值运算符，大数之间赋值运算
{
    int i;
    len=n.len;
    memset(a,sizeof(a));
    for(i=0;i<len;i++)
        a[i]=n.a[i];
    return *this;
}
istream& operator>>(istream &in,BigNum &b)
{
    char ch[MAXSIZE*4];
    int i=-1;
    in>>ch;
    int L=strlen(ch);
    int count=0,sum=0;
    for(i=L-1;i>=0;)
    {
        sum=0;
        int t=1;
        for(int j=0;j<4&&i>=0;j++,i--,t*=10)
        {
            sum+=(ch[i]-'0')*t;
        }
        b.a[count]=sum;
        count++;
    }
    b.len=count++;
    return in;
}
ostream& operator<<(ostream& out,BigNum& b)  //重载输出运算符
{
    int i;
    cout<<b.a[b.len-1];
    for(i=b.len-2;i>=0;i--)
    {
        printf("%04d",b.a[i]);
    }
    return out;
}
BigNum BigNum::operator+(const BigNum &T)const   //两个大数之间的相加运算
{
    BigNum t(*this);
    int i,big;
    big=T.len>len?T.len:len;
    for(i=0;i<big;i++)
    {
        t.a[i]+=T.a[i];
        if(t.a[i]>MAXN)
        {
            t.a[i+1]++;
            t.a[i]-=MAXN+1;
        }
    }
    if(t.a[big]!=0)
       t.len=big+1;
    else t.len=big;
    return t;
}
BigNum BigNum::operator-(const BigNum &T)const  //两个大数之间的相减运算
{
    int i,j,big;
    bool flag;
    BigNum t1,t2;
    if(*this>T)
    {
        t1=*this;
        t2=T;
        flag=0;
    }
    else
    {
        t1=T;
        t2=*this;
        flag=1;
    }
    big=t1.len;
    for(i=0;i<big;i++)
    {
        if(t1.a[i]<t2.a[i])
        {
            j=i+1;
            while(t1.a[j]==0)
                j++;
            t1.a[j--]--;
            while(j>i)
                t1.a[j--]+=MAXN;
            t1.a[i]+=MAXN+1-t2.a[i];
        }
        else t1.a[i]-=t2.a[i];
    }
    t1.len=big;
    while(t1.a[len-1]==0 && t1.len>1)
    {
        t1.len--;
        big--;
    }
    if(flag)
        t1.a[big-1]=0-t1.a[big-1];
    return t1;
}
BigNum BigNum::operator*(const BigNum &T)const  //两个大数之间的相乘
{
    BigNum ret;
    int i,up;
    int temp,temp1;
    for(i=0;i<len;i++)
    {
        up=0;
        for(j=0;j<T.len;j++)
        {
            temp=a[i]*T.a[j]+ret.a[i+j]+up;
            if(temp>MAXN)
            {
                temp1=temp-temp/(MAXN+1)*(MAXN+1);
                up=temp/(MAXN+1);
                ret.a[i+j]=temp1;
            }
            else
            {
                up=0;
                ret.a[i+j]=temp;
            }
        }
        if(up!=0)
           ret.a[i+j]=up;
    }
    ret.len=i+j;
    while(ret.a[ret.len-1]==0 && ret.len>1)ret.len--;
    return ret;
}
BigNum BigNum::operator/(const int &b)const  //大数对一个整数进行相除运算
{
    BigNum ret;
    int i,down=0;
    for(i=len-1;i>=0;i--)
    {
        ret.a[i]=(a[i]+down*(MAXN+1))/b;
        down=a[i]+down*(MAXN+1)-ret.a[i]*b;
    }
    ret.len=len;
    while(ret.a[ret.len-1]==0 && ret.len>1)
        ret.len--;
    return ret;
}
int BigNum::operator%(const int &b)const   //大数对一个 int类型的变量进行取模
{
    int i,d=0;
    for(i=len-1;i>=0;i--)
        d=((d*(MAXN+1))%b+a[i])%b;
    return d;
}
BigNum BigNum::operator^(const int &n)const  //大数的n次方运算
{
    BigNum t,ret(1);
    int i;
    if(n<0)exit(-1);
    if(n==0)return 1;
    if(n==1)return *this;
    int m=n;
    while(m>1)
    {
        t=*this;
        for(i=1;(i<<1)<=m;i<<=1)
           t=t*t;
        m-=i;
        ret=ret*t;
        if(m==1)ret=ret*(*this);
    }
    return ret;
}
bool BigNum::operator>(const BigNum &T)const    //大数和另一个大数的大小比较
{
    int ln;
    if(len>T.len)return true;
    else if(len==T.len)
    {
        ln=len-1;
        while(a[ln]==T.a[ln]&&ln>=0)
          ln--;
        if(ln>=0 && a[ln]>T.a[ln])
           return true;
        else
           return false;
    }
    else
       return false;
}
bool BigNum::operator>(const int &t)const  //大数和一个int类型的变量的大小比较
{
    BigNum b(t);
    return *this>b;
}
void BigNum::print()   //输出大数
{
    int i;
    printf("%d",a[len-1]);
    for(i=len-2;i>=0;i--)
      printf("%04d",a[i]);
    printf("n");
}
bool ONE(BigNum a)
{
    if(a.len == 1 && a.a[0] == 1)return true;
    else return false;
}
BigNum A,Y;
char str1[10010],str2[10010],str3[10010],str4[10010];


int a[1010],b[1010],x[1010],y[1010];
int c[1010];
int main()
{
    //freopen("in.txt",stdin);
    //freopen("out.txt",stdout);
    int T;
    int n;
    int iCase = 0;
    scanf("%d",&T);
    while(T--)
    {
        iCase++;
        scanf("%d",&n);
        cin>>A>>X>>B>>Y;
        printf("Case %d: ",iCase) ;
        A = A-1;
        X = X-1;
        B = B-1;
        Y = Y-1;
        for(int i = 0;i < n;i++)
        {
            if(A.a[0]%2 == 0)a[i] = 0;
            else a[i] = 1;
            if(B.a[0]%2 == 0)b[i] = 0;
            else b[i] = 1;
            if(X.a[0]%2 == 0)x[i] = 0;
            else x[i] = 1;
            if(Y.a[0]%2 == 0)y[i] = 0;
            else y[i] = 1;
            A = A/2;
            B = B/2;
            X = X/2;
            Y = Y/2;
        }
        bool flag = false;
        for(int k = 0;k <= n;k++)
        {
            x[n] = x[0];
            y[n] = y[0];
            for(int i = 0;i < n;i++)
            {
                x[i] = x[i+1];
                y[i] = y[i+1];
            }
            for(int i = 0;i < n;i++)
            {
                if(a[i] == x[i])c[i] = 0;
                else c[i] = 1;
            }
            bool fff = true;
            for(int i = 0;i < n;i++)
                if(b[i]^c[i] != y[i])
                {
                    fff = false;
                    break;
                }
            if(fff)flag = true;
            if(flag)break;

        }
        if(flag)printf("Yesn");
        else printf("Non");
    }
    return 0;
}

//题目意思很简单。


就是洗牌，抽出奇数和偶数，要么奇数放前面，要么偶数放前面。


?


总共2^N张牌。


需要问的是，给了A X B Y ?问经过若干洗牌后，第A个位置是X，第B个位置是Y 是不是可能的。


?


题目给的牌编号是1开始的，先转换成0开始。


一开始位置是0~2^N-1. ?对应的牌是0~2^N-1


首先来看每次洗牌的过程。


对于第一种洗牌：将奇数放前面，偶数放后面。其实每个位置数的变化就是相当于循环右移一位，然后高位异或1.


对于第二种洗牌：讲偶数放前面，奇数放后面。其实每个位置数的变化就是相当于循环右移一位，然后高位异或0.


?


所以经过若干次洗牌，可以看成是循环右移了K位，然后异或上一个数。


?


所以对于题目的查询：


首先将A X B Y都减一。 ?然后枚举X,Y循环右移了K位以后，能不能同时异或上相同的数得到A,B


?


需要大数，然后转化成二进制就可以解决了。


循环右移X,Y，然后判断A ^ X 是不是等于 B ^ Y

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!