高精：

#include
    
     #define int long longusing namespace std;const int MAXN=100000,B=100000000,MAXM=3000;int A[MAXN+5];namespace Huge_int {    using namespace std;    struct huge_int {        int n;        int a[MAXM+5];        inline void clear() { memset(a,0,sizeof(a));n=0; }        inline void work() { while(n>1 && !a[n]) n--; }        inline huge_int rd() {            memset(A,0,sizeof(A));            clear();            char ch=getchar();            while(ch<'0' || ch>'9') ch=getchar();            while(ch<='9' && ch>='0') A[++n]=ch-'0',ch=getchar();            for(int i=1;i+i<=n;++i) swap(A[i],A[n-i+1]);            for(int i=1;i<=n;i+=8){                int j=(i+7)/8;                a[j]=(A[i]+A[i+1]*10+A[i+2]*100+A[i+3]*1000+A[i+4]*10000+A[i+5]*100000+A[i+6]*1000000+A[i+7]*10000000);            }            n=(n+7)/8;            return *this;        }        inline huge_int wrt() const {            printf("%lld",a[n]);            for(int i=n-1;i>=1;--i) printf("%08lld",a[i]);            putchar('\n');            return *this;        }        inline bool operator < (const huge_int &nt) const {            if(n
     
      nt.n) return 0;            for(int i=n;i>=1;--i)                if(a[i]!=nt.a[i])return a[i]
      
        (const huge_int &nt) const {            return nt<*this;        }        inline bool operator != (const huge_int &nt) const {            return (*this
       
        =1;--i){                x=x*B+a[i];                tmp.a[i]=x/nt;                x%=nt;            }            tmp.work();            return tmp;        }        inline huge_int operator += (const huge_int &nt) { return *this=*this+nt; }        inline huge_int operator -= (const huge_int &nt) { return *this=*this-nt; }        inline huge_int operator *= (const huge_int &nt) { return *this=*this*nt; }        inline huge_int operator /= (const int      &nt) { return *this=*this/nt; }    };    inline huge_int gcd(huge_int a,huge_int b) {        int na=0,nb=0;        while(!(a.a[1]&1)) na++,a/=2;        while(!(b.a[1]&1)) nb++,b/=2;        int x=min(na,nb);        while(a!=b){            if(a
       
      
     
    

矩阵乘法和快速幂：

namespace Matrix {    using namespace std;    const int p=2009;    struct matrix {        int a[MAXN+5][MAXN+5];        int n,m;        inline void set(const int &nx) {            for(int i=1;i<=nx;++i) a[i][i]=1;            n=m=nx;        }        inline void clear(){ n=m=0;memset(a,0,sizeof(a)); }        inline matrix operator * (const matrix &b) const {            matrix ret;ret.clear();            ret.n=n;ret.m=b.m;            for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)for(int k=1;k<=b.m;++k)                ret.a[i][j]=(ret.a[i][j]+a[i][k]*b.a[k][j]%p)%p;            return ret;        }        inline matrix operator *= (const matrix &b) { return *this=*this*b; }        inline void wrt() {            for(int i=1;i<=n;++i){                for(int j=1;j<=m;++j) printf("%d ",a[i][j]);                putchar('\n');            }        }    };    inline matrix power(matrix a,int b) {        matrix ret;ret.clear();ret.set(a.n);        for(;b;a*=a,b>>=1)if(b&1)ret*=a;        return ret;    }}

拉链hash：

namespace Hash{    const int mod=100007;    struct HashTable {        struct Link { int val1,val2,next;}E[N];        int head[mod],cnt;        inline void add(int u,int v,int w) {            E[++cnt].next=head[u];            E[cnt].val1=v;            E[cnt].val2=w;            head[u]=cnt;        }        inline void insert(int x,int k) {            int s=x%mod;            add(s,x,k);        }        inline void clear() {            memset(head,0,sizeof(head));            cnt=0;        }        inline int locate(int x) {            int s=x%mod;            for(int i=head[s];i;i=E[i].next)                if(E[i].val1==x) return E[i].val2;            return -1;        }    }H;}