poj-3982(矩阵快速幂+大数模板)

待我称王封你为后i 2022-06-09 04:25 242阅读 0赞

问题描述:

数列A满足An = An-1 + An-2 + An-3, n >= 3 ,编写程序，给定A0, A1 和 A2, 计算A99

Input

输入包含多行数据   
每行数据包含3个整数A0, A1, A2 (0 <= A0, A1, A2 <= 32767)   
数据以EOF结束

Output

对于输入的每一行输出A99的值

Sample Input

1 1 1

Sample Output

69087442470169316923566147

题目题意:题目题意很简单，就是求A99.

题目分析:因为存在递推式的缘故，很自然的想到了矩阵快速幂来加速递推，但是这不是这道题目的关键，这道题目的范围，数据范围很大，导致没办法用普通数据范围来保存，所以大数的模板就很重要了。这道题目主要想分享一下这个大数模板.

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<string>
    using namespace std;
    
    const int MAXN =510;
    
    struct bign
    {
        int len, s[MAXN];
        bign ()
        {
            memset(s, 0, sizeof(s));
            len = 1;
        }
        bign (int num) { *this = num; }
        bign (const char *num) { *this = num; }
        bign operator = (const int num)
        {
            char s[MAXN];
            sprintf(s, "%d", num);
            *this = s;
            return *this;
        }
        bign operator = (const char *num)
        {
            for(int i = 0; num[i] == '0'; num++) ;  //去前导0
            len = strlen(num);
            for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
            return *this;
        }
        bign operator + (const bign &b) const //+
        {
            bign c;
            c.len = 0;
            for(int i = 0, g = 0; g || i < max(len, b.len); i++)
            {
                int x = g;
                if(i < len) x += s[i];
                if(i < b.len) x += b.s[i];
                c.s[c.len++] = x % 10;
                g = x / 10;
            }
            return c;
        }
        bign operator += (const bign &b)
        {
            *this = *this + b;
            return *this;
        }
        void clean()
        {
            while(len > 1 && !s[len-1]) len--;
        }
        bign operator * (const bign &b) //*
        {
            bign c;
            c.len = len + b.len;
            for(int i = 0; i < len; i++)
            {
                for(int j = 0; j < b.len; j++)
                {
                    c.s[i+j] += s[i] * b.s[j];
                }
            }
            for(int i = 0; i < c.len; i++)
            {
                c.s[i+1] += c.s[i]/10;
                c.s[i] %= 10;
            }
            c.clean();
            return c;
        }
        bign operator *= (const bign &b)
        {
            *this = *this * b;
            return *this;
        }
        bign operator - (const bign &b)
        {
            bign c;
            c.len = 0;
            for(int i = 0, g = 0; i < len; i++)
            {
                int x = s[i] - g;
                if(i < b.len) x -= b.s[i];
                if(x >= 0) g = 0;
                else
                {
                    g = 1;
                    x += 10;
                }
                c.s[c.len++] = x;
            }
            c.clean();
            return c;
        }
        bign operator -= (const bign &b)
        {
            *this = *this - b;
            return *this;
        }
        bign operator / (const bign &b)
        {
            bign c, f = 0;
            for(int i = len-1; i >= 0; i--)
            {
                f = f*10;
                f.s[0] = s[i];
                while(f >= b)
                {
                    f -= b;
                    c.s[i]++;
                }
            }
            c.len = len;
            c.clean();
            return c;
        }
        bign operator /= (const bign &b)
        {
            *this  = *this / b;
            return *this;
        }
        bign operator % (const bign &b)
        {
            bign r = *this / b;
            r = *this - r*b;
            return r;
        }
        bign operator %= (const bign &b)
        {
            *this = *this % b;
            return *this;
        }
        bool operator < (const bign &b)
        {
            if(len != b.len) return len < b.len;
            for(int i = len-1; i >= 0; i--)
            {
                if(s[i] != b.s[i]) return s[i] < b.s[i];
            }
            return false;
        }
        bool operator > (const bign &b)
        {
            if(len != b.len) return len > b.len;
            for(int i = len-1; i >= 0; i--)
            {
                if(s[i] != b.s[i]) return s[i] > b.s[i];
            }
            return false;
        }
        bool operator == (const bign &b)
        {
            return !(*this > b) && !(*this < b);
        }
        bool operator != (const bign &b)
        {
            return !(*this == b);
        }
        bool operator <= (const bign &b)
        {
            return *this < b || *this == b;
        }
        bool operator >= (const bign &b)
        {
            return *this > b || *this == b;
        }
        string str() const
        {
            string res = "";
            for(int i = 0; i < len; i++) res = char(s[i]+'0') + res;
            return res;
        }
    };
    
    istream& operator >> (istream &in, bign &x)
    {
        string s;
        in >> s;
        x = s.c_str();
        return in;
    }
    
    ostream& operator << (ostream &out, const bign &x)
    {
        out << x.str();
        return out;
    }//大数模板
    
    struct matrix//构建矩阵
    {
        bign f[4][4];
        matrix operator *( matrix &a) {
            matrix res;
            for (int i=1;i<=3;i++) {
                for (int j=1;j<=3;j++) {
                    res.f[i][j]=0;
                    for (int k=1;k<=3;k++)
                      res.f[i][j]+=f[i][k]*a.f[k][j];
                }
            }
            return res;
        }
    }a,b;
    int a0,a1,a2;
    void init()
    {
        b.f[1][1]=b.f[1][2]=b.f[1][3]=1;
        b.f[2][1]=1;
        b.f[3][2]=1;
        a.f[1][1]=a2,a.f[2][1]=a1,a.f[3][1]=a0;
    }
    
    matrix fast_pow(matrix base,int k)//快速幂
    {
        matrix ans;
        for (int i=1;i<=3;i++)
            ans.f[i][i]=1;
        while (k) {
            if (k&1)
              ans=ans*base;
            base=base*base;
            k>>=1;
        }
        return ans;
    }
    int main()
    {
        while (scanf("%d%d%d",&a0,&a1,&a2)!=EOF) {
            init();
            matrix cur,ans;
            cur=b;
            cur=fast_pow(cur,97);
            ans=cur*a;
            cout<<ans.f[1][1]<<endl;
        }
        return 0;
    }