快读

update4: 可以用 read<int>() 获得一个 int 型数据，或者 read<long long>() 获得一个 long long 型数据,
即 a = read<int>() ，但是只能读整数，不要传入字符串或浮点数

update3: 已通过 #ifdef 方式实现在OJ上用 fread ,在本地上用 cstdio 库输入输出，本地debug不需要文件读写了

update2: 可以用 io>>a>>b , io<<a<<b, io>>a<<a ，还写上了 #define cin io , #define cout io , #define endl '\n' ，使用cin的话可以直接把板子贴上去无需修改

update1: 已修复无法while(read())的bug

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO
{
    #define FASTIO
    #define IOSIZE 100000
    char ibuf[IOSIZE], obuf[IOSIZE];
    char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
    #ifdef ONLINE_JUDGE
        #define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
        #define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
    #endif//fread in OJ, stdio in local
    
    #define isdigit(ch) (ch>47&&ch<58)
    #define isspace(ch) (ch<33)
    template<typename T> inline T read()
    {
        T s = 0; int w = 1; char ch;
        while(ch=getchar(),!isdigit(ch)and(ch!=EOF)) if(ch=='-') w=-1;
        if(ch == EOF) return false;
        while(isdigit(ch)) s=s*10+ch-48,ch=getchar();
        return s*w;
    }
    template<typename T> inline bool read(T &s)
    {
        s = 0; int w = 1; char ch;
        while(ch=getchar(),!isdigit(ch)and(ch!=EOF)) if(ch=='-') w=-1;
        if(ch == EOF) return false;
        while(isdigit(ch)) s=s*10+ch-48,ch=getchar();
        return s*=w, true;
    }
    inline bool read(char &s)
    {
        while(s = getchar(), isspace(s));
        return true;
    }
    inline bool read(char *s)
    {
        char ch;
        while(ch=getchar(),isspace(ch));
        if(ch == EOF) return false;
        while(!isspace(ch)) *s++ = ch, ch = getchar();
        *s = '\000'; return true;
    }
    template<typename T> inline void print(T x)
    {
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) print(x/10);
        putchar(x%10+48);
    }
    inline void print(char x){ putchar(x); }
    inline void print(char *x){ while(*x) putchar(*x++); }
    inline void print(const char *x)
    { for(int i = 0; x[i]; i++) putchar(x[i]); }
    #ifdef _GLIBCXX_STRING//string
        inline bool read(std::string& s)
        {
            s = ""; char ch;
            while(ch=getchar(),isspace(ch));
            if(ch == EOF) return false;
            while(!isspace(ch)) s += ch, ch = getchar();
            return true;
        }
        inline void print(std::string x)
        {
            for(int i = 0, n = x.size(); i < n; i++)
                putchar(x[i]);
        }
    #endif
    template<typename T, typename... T1> inline int read(T& a, T1&... other){ return read(a)+read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other){ print(a); print(other...); }

    struct fast_IO_t{
        ~fast_IO_t(){ fwrite(obuf, p3-obuf, 1, stdout); }
        bool flag = false;
        operator bool(){ return flag; }
    }io;
    template<typename T> fast_IO_t& operator >> (fast_IO_t &io, T &b){ return io.flag = read(b), io; }
    template<typename T> fast_IO_t& operator << (fast_IO_t &io, T b){ return print(b), io; }
    #define cout io
    #define cin io
    #define endl '\n'
}
using namespace fast_IO;

高精

支持除位运算符外所有运算符，请通过修改bigint_SIZE来修改高精数长度

tips: 除法有一点慢

输入输出可以用成员函数(bigint).input()和(bigint).print()，也可以用read(bigint&)和print(bigint)

namespace bigint_space{
    const int bigint_SIZE = 505;
    char bigint_input[bigint_SIZE];
    bool division_compare(short *a, int lena, short *b, int lenb)
    {
        if(lena != lenb)
            return lena > lenb;
        for(int i = 1; i <= lena; i++)
        {
            if(a[i] != b[i])
                return a[i] > b[i];
        }
        return true;
    }
    void division_minus(short *a, int lena, short *b, int lenb)
    {
        int f = lena != lenb;
        for(int i = lena; i >= 1; i--)
        {
            a[i] -= b[i-f];
            if(a[i] < 0)
                a[i] += 10, a[i-1]--;
        }
    }
    class bigint{
        private:
            int len;
            short s[bigint_SIZE];
            bool less0;
        public:
            bigint(long long x = 0)
            {
                std::memset(s, 0, sizeof(s));
                len = 0; less0 = false;
                if(x == 0)
                {
                    len = 1;
                    return;
                }
                if(x < 0)
                    less0 = true, x = -x;
                while(x != 0)
                    s[++len] = x%10, x /= 10;
            }
            void clear(){ std::memset(s,0,sizeof(s)); len=1; }
            void input()
            {
                std::memset(s, 0, sizeof(s));
                std::memset(bigint_input, 0, sizeof(bigint_input));
                len = 0;
                char ch = getchar();
                while(!isdigit(ch))
                {
                    if(ch == '-')
                        less0 = true;
                    ch = getchar();
                }
                while(isdigit(ch))
                {
                    bigint_input[++len] = ch;
                    ch = getchar();
                }
                for(int i = 1; i <= len; i++)
                    s[i] = bigint_input[len-i+1]-48;
                #ifdef getchar
                    ibufp1--;
                #endif
            }
            void print()
            {
                if(less0) putchar('-');
                for(int i = len; i >= 1; i--)
                    putchar(s[i]+48);
            }
            friend bigint operator + (bigint a, bigint b)
            {
                bigint c;
                c.len = a.len > b.len ? a.len : b.len;
                if(a.less0 && b.less0)
                    return -(-a + -b);
                if(a.less0)
                    return b-abs(a);
                if(b.less0)
                    return a-abs(b);
                
                for(int i = 1; i <= c.len+1; i++)
                {
                    c.s[i] += a.s[i]+b.s[i];
                    c.s[i+1] += c.s[i]/10;
                    c.s[i] %= 10;
                }
                if(c.s[c.len+1] != 0)
                c.len++;
                return c;
            }
            friend bigint operator - (bigint a)
            {
                a.less0 = !a.less0;
                return a;
            }
            friend bigint operator - (bigint a, bigint b)
            {
                if(b.less0)
                    return a+abs(b);
                if(a.less0)
                    return -(abs(a)+b);
                if(a < b)
                    return -(b-a);
                bigint c;
                c.len = a.len > b.len ? a.len : b.len;
                for(int i = 1; i <= c.len; i++)
                {
                    c.s[i] = a.s[i]-b.s[i];
                    if(c.s[i] < 0)
                        a.s[i+1]--, c.s[i] += 10;
                }
                while(c.s[c.len] == 0 and c.len > 1)
                    c.len--;
                return c;
            }
            friend bigint operator * (bigint a, bigint b)
            {
                bigint c;
                c.less0 = a.less0 ^ b.less0;
                for(int i = 1; i <= b.len; i++)
                    for(int j = 1; j <= a.len; j++)
                        c.s[i+j-1] += a.s[j]*b.s[i];
                c.len = a.len+b.len;
                for(int i = 1; i <= c.len; i++)
                {
                    c.s[i+1] += c.s[i]/10;
                    c.s[i] %= 10;
                }
                while(c.s[c.len] == 0 and c.len > 1)
                    c.len--;
                return c;
            }
            friend bigint operator / (bigint a, long long b)
            {
                if(abs(a) < abs(b))
                    return 0;
                bigint c;
                c.len = a.len;
                long long tot = 0;
                for(int i = a.len; i >= 1; i--)
                {
                    tot *= 10;
                    tot += a.s[i];
                    if(tot >= b)
                    {
                        c.s[i] = tot/b;
                        tot %= b;
                    }
                }
                while(c.s[c.len] == 0 and c.len > 1)
                    c.len--;
                c.less0 = a.less0 ^ (b<0);
                return c;
            }
            friend bigint operator / (bigint a,bigint b)
            {
                if(abs(a) < abs(b))
                    return 0;
                bigint c;
                c.len = a.len-b.len+1;
                c.less0 = a.less0 ^ b.less0;
                short abuf[bigint_SIZE]; int top = 0;
                short bbuf[bigint_SIZE];
                memset(abuf, 0, sizeof(abuf));
                memset(bbuf, 0, sizeof(bbuf));
                for(int i = b.len; i >= 1; i--)
                    bbuf[i] = b.s[b.len-i+1];
                for(int i = a.len; i >= 1;)
                {
                    while(!division_compare(abuf, top, bbuf, b.len) and i > 0)
                    {
                        if(!(top == 0 and a.s[i] == 0))
                            abuf[++top] = a.s[i];
                        i--;
                    }
                    while(division_compare(abuf, top, bbuf, b.len))
                    {
                        division_minus(abuf, top, bbuf, b.len);
                        c.s[i+1]++;
                        int tot = 0;
                        for(int j = 1; j <= top; j++)
                        {
                            if(abuf[j] != 0)
                                break;
                            tot++;
                        }
                        if(tot != 0)
                        {
                            for(int j = 1; j <= top-tot; j++)
                                abuf[j] = abuf[j+tot], abuf[j+tot] = 0;
                            top -= tot;
                        }
                    }
                }
                while(c.s[c.len] == 0 and c.len > 1)
                    c.len--;
                return c;
            }
            friend bigint operator % (bigint a, bigint b)
            {
                bigint c;
                c.less0 = 0;
                short abuf[bigint_SIZE]; int top = 0;
                short bbuf[bigint_SIZE];
                memset(abuf, 0, sizeof(abuf));
                memset(bbuf, 0, sizeof(bbuf));
                for(int i = b.len; i >= 1; i--)
                    bbuf[i] = b.s[b.len-i+1];
                for(int i = a.len; i >= 1;)
                {
                    while(!division_compare(abuf, top, bbuf, b.len) and i > 0)
                    {
                        if(!(top == 0 and a.s[i] == 0))
                            abuf[++top] = a.s[i];
                        i--;
                    }
                    while(division_compare(abuf, top, bbuf, b.len))
                    {
                        division_minus(abuf, top, bbuf, b.len);
                        int tot = 0;
                        for(int j = 1; j <= top; j++)
                        {
                            if(abuf[j] != 0)
                                break;
                            tot++;
                        }
                        if(tot != 0)
                        {
                            for(int j = 1; j <= top-tot; j++)
                                abuf[j] = abuf[j+tot], abuf[j+tot] = 0;
                            top -= tot;
                        }
                    }
                }
                c.len = (top==0)?1:top;
                for(int i = top; i >= 1; i--)
                    c.s[top-i+1] = abuf[i];
                while(c.s[c.len] == 0 and c.len > 1)
                    c.len--;
                return c;
            }
            friend bigint operator ++ (bigint &a) { return (a = a+1); }
            bigint operator ++ (int){
                bigint a = *this;
                *this = (*this)+1;
                return a;
            }
            friend bigint operator -- (bigint &a) { return (a = a-1); }
            bigint operator -- (int){
                bigint a = *this;
                *this = *this - 1;
                return a;
            }
            bigint operator = (long long x){
                std::memset(s, 0, sizeof(s));
                len = 0; less0 = false;
                if(x == 0)
                {
                    len = 1;
                    return *this;
                }
                if(x < 0)
                    less0 = true, x = -x;
                while(x != 0)
                    s[++len] = x%10, x /= 10;
                return *this;
            }
            friend bool operator > (bigint a, bigint b)
            {
                if(a.less0 != b.less0)
                    return a.less0 < b.less0;
                bool ans = false;
                if(a.len != b.len)
                    ans = a.len > b.len;
                else
                {
                    for(int i = a.len; i >= 1; i--)
                        if(a.s[i] != b.s[i])
                        {
                            ans = a.s[i] > b.s[i];
                            break;
                        }
                }
                return (a.less0 and b.less0) ? !ans : ans;
            }
            friend bool operator < (bigint a, bigint b)
            {
                if(a.less0 != b.less0)
                    return a.less0 > b.less0;
                bool ans = false;
                if(a.len != b.len)
                    ans = a.len < b.len;
                else
                {
                    for(int i = a.len ; i >= 1; i--)
                        if(a.s[i] != b.s[i])
                        {
                            ans = a.s[i] < b.s[i];
                            break;
                        }
                }
                return (a.less0 and b.less0) ? !ans : ans;
            }
            friend bool operator == (bigint a, bigint b)
            {
                if(a.less0 != b.less0)
                    return false;
                if(a.len != b.len)
                    return false;
                for(int i = 1; i <= a.len; i++)
                    if(a.s[i] != b.s[i])
                        return false;
                return true;
            }
            friend bool operator >= (bigint a, bigint b) { return !(a<b); }
            friend bool operator <= (bigint a, bigint b) { return !(a>b); }
            friend bool operator != (bigint a, bigint b) { return !(a==b); }
            friend bigint max(bigint a, bigint b){ return a>b?a:b; }
            friend bigint min(bigint a, bigint b){ return a<b?a:b; }
            friend bigint abs(bigint a){ a.less0 = false; return a; }
            bigint operator += (bigint a){ return *this = *this+a; }
            bigint operator -= (bigint a){ return *this = *this-a; }
            bigint operator *= (bigint a){ return *this = *this*a; }
            bigint operator /= (bigint a){ return *this = *this/a; }
            bigint operator %= (bigint a){ return *this = *this%a; }
    };
    void read(bigint &a){ a.input(); }
    void print(bigint a) { a.print(); }
}
using namespace bigint_space;

矩阵运算

声明一个矩阵: matrix a;

支持 + , - , * , % , 下标访问和快速幂.

注意：为了方便debug，在不满足运算法则进行运算时会直接退出程序并输出 Matrix error!

默认矩阵大小为 Xsize , Ysize ，可自行修改
我也写了构造函数，可以用 matrix a(10,10) 来手动规定矩形的长和宽.

默认情况下矩阵内全为0，可以通过下标访问修改矩阵内元素的值.

默认情况下矩阵内元素类型为 int ，可以修改 #define type int 来修改元素类型.

默认情况下矩阵自动对 INT_MAX 取模，你也可以修改这个自动模数，在 const type mod = INT_MAX 处可以修改.

为了debug方便你可以直接 print(matrix) 来输出一个矩阵.

我内部是用一个 vector<vector<type>> 实现的矩阵，常数有点大请见谅，但是我找不到更好的写法来实现矩阵了，如果有速度更快的办法可以私信我，我尽量更新(

namespace Matrix
{
    #define type int
    const int Xsize = 80;
    const int Ysize = 80;
    const type mod = INT_MAX;    
    struct matrix
    {
        vector<vector<type>> a;
        int xlen, ylen;
        matrix(int x=Xsize, int y=Ysize)
        {
            xlen = x, ylen = y;
            a.resize(x+1);
            for(int i = 1; i <= x; i++)
            {
                a[i].resize(y+1);
                a[i].assign(y+1, 0);
            }
        }
        vector<type>& operator [] (int x)
        {
            return a[x];
        }
    };
    void throw_error()
    {
        cout << "Matrix error!";
        std::exit(0);
    }
    matrix operator + (matrix a, matrix b)
    {
        if(a.xlen != b.xlen or a.ylen != b.ylen)
            throw_error();
        for(int i = 1; i <= a.xlen; i++)
        for(int j = 1; j <= a.ylen; j++)
            (a[i][j] += b[i][j]) %= mod;
        return a;
    }
    matrix operator - (matrix a, matrix b)
    {
        if(a.xlen != b.xlen or a.ylen != b.ylen)
            throw_error();
        for(int i = 1; i <= a.xlen; i++)
        for(int j = 1; j <= a.ylen; j++)
            (a[i][j] -= b[i][j]) %= mod;
        return a;
    }
    matrix operator * (matrix a, matrix b)
    {
        if(a.ylen != b.xlen) throw_error();
        matrix ans(a.xlen, b.ylen);
        for(int i = 1; i <= a.xlen; i++)
        for(int j = 1; j <= b.ylen; j++)
        for(int k = 1; k <= a.ylen; k++)
            (ans[i][j] += a[i][k]*b[k][j]) %= mod;
        return ans;
    }
    matrix operator * (matrix a, type k)
    {
        for(int i = 1; i <= a.xlen; i++)
        for(int j = 1; j <= a.ylen; j++)
            (a[i][j] *= k) %= mod;
        return a;
    }
    matrix operator % (matrix a, type k)
    {
        for(int i = 1; i <= a.xlen; i++)
        for(int j = 1; j <= a.ylen; j++)
            a[i][j] %= k;
        return a;
    }
    matrix& operator += (matrix &a, matrix b){ return (a = a+b); }
    matrix& operator -= (matrix &a, matrix b){ return (a = a-b); }
    matrix& operator *= (matrix &a, matrix b){ return (a = a*b); }
    matrix& operator *= (matrix &a, type k){ return (a = a*k); }
    matrix& operator %= (matrix &a, type k){ return (a = a%k); }
    matrix pow(matrix a, long long p, type k=mod)
    {
        if(a.xlen != a.ylen) throw_error();
        matrix ans(a.xlen, a.ylen);
        for(int i = 1; i <= a.xlen; i++)
            ans[i][i] = 1;
        for(; p; p >>= 1, (a *= a) %= k)
            if(p&1) (ans *= a) %= k;
        return ans;
    }
    void print(matrix a)
    {
        for(int i = 1; i <= a.xlen; i++)
        {
            for(int j = 1; j <= a.ylen; j++)
                cout << a[i][j] << ' ';
            cout << endl;
        }
    }
}
using namespace Matrix;