Skip to content

高精度

~~我愿称之为史上最烦人的算法~~

__int128

~~虽然理论上只能在linux环境中用，不知道考试时CCF的老年机能不能编译通过，但洛谷是可以的~~

本质就是一个128位的大整数，大约40位，对于小部分对高精度要求较$_ { 小} $的题是可以用的，省事。

gcc中官方给出的__int128有两种,为 

__int128_t a=10000000000000L;
__uint128_t b=200000000000000L;
//__int128 c=100000000000L
a*=b;//long long 溢出，但__int128不会
~~事实上__int128和__int128_t都能用~~

运算的话，同样支持取反，异或，位移，加减乘除等。 就是输入输出要用快写快读

#define int __int128
int read1(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9' || ch<'0'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void write1(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write1(x/10);
    putchar(x%10+'0');
    return;
}

P1005

1.__int128 

#include<iostream>
#include<cstdio>
#include<cstring>
#define int __int128_t
using namespace std;
const int N=110;
int n,m;
int f[N][N],a[N][N],tmp[N];
int kp(int x,int p){
    if(p<=1)return x;
    if(p%2==0)return kp(x*x,p>>1);
    else return x*kp(x*x,p>>1);
}
int dp(int x){
    memset(f,0,sizeof f);
    for(int i=1;i<=m;++i)tmp[i]=a[x][i];
    tmp[0]=tmp[m+1]=0;
    for(int i=1;i<=m;++i){
        f[i][i]=tmp[i]<<1;
    }
    for(int l=2;l<=m;++l){
        for(int b=1;b+l-1<=m;++b){
            int e=b+l-1;
            f[b][e]=max(f[b][e],2*f[b][e-1]+2*tmp[e]);
            f[b][e]=max(f[b][e],2*f[b+1][e]+2*tmp[b]);
        }
    }
    return f[1][m];
}
int read1(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9' || ch<'0'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void write1(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write1(x/10);
    putchar(x%10+'0');
    return;
}
signed main(){
    n=read1(),m=read1();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            a[i][j]=read1();
        }
    }
    int ans=0; 
    for(int i=1;i<=n;++i){
        int tmp=dp(i);
        //write1(tmp);
        //putchar('\n');
        ans+=tmp;
    }
    write1(ans);
    return 0; 
}
/*
5 5
0 0 0 0 0
0 0 0 0 1
876 1 566 920 598
259 945 123 659 997
176 478 293 464 278
2 3
1 5 2
3 4 2
2 4
1 4 2 3
1 4 3 2
*/
2.朴素 
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=110;
int n,m;
struct HP{
    int p[N],len;
    void clear1(){
        memset(p,0,sizeof p);
        len=1;
        return;
    }
    void read1(){
        memset(p,0,sizeof p);
        len=1;
        p[0]=1;
        char ch=getchar();
        while(ch>'9' || ch<'0'){
            if(ch=='-')p[0]=-1;
            ch=getchar();
        }
        while(ch<='9' && ch>='0'){
            p[++len]=ch-'0';
            ch=getchar();
        }
        for(int i=1;i<=len/2;++i){
            swap(p[i],p[len-i+1]);
        }
    }
    void write1(){
        if(p[0]==-1)putchar('-');
        for(int i=len;i>=1;--i){
            putchar(p[i]+'0');
        }
        putchar('\n');
    }
}f[N][N],a[N][N],tmp[N],ans,tp;
HP operator +(const HP &a,const HP &b){
    //if(a.p[0]==-1 || b.p[0]==-1)return a-b;
    HP c;
    c.clear1();
    int la=a.len,lb=b.len,lc=max(la,lb);
    int f=0;
    for(int i=1;i<=lc;++i){
        c.p[i]=a.p[i]+b.p[i]+f;
        f=c.p[i]/10;
        c.p[i]%=10;
    }
    if(f)c.p[++lc]=f;
    c.len=lc;
    return c;
}
int cmp(const HP &a,const HP &b){
    //cout<<a.len<<" "<<b.len<<endl;
    if(a.len<b.len)return -1;
    if(a.len>b.len)return 1;
    for(int i=a.len;i>=1;--i){
        if(a.p[i]<b.p[i])return -1;
        if(a.p[i]>b.p[i])return 1;
    }
    return 0;
}
HP max1(const HP &a,const HP &b){
    int res=cmp(a,b);
    if(res>=0)return a;
    else return b;
}
HP operator -(const HP &x,const HP &y){
    HP c,a,b;
    c.clear1();
    if(cmp(x,y)==-1){
        a=y,b=x;
        c.p[0]=-1;  
    }else{
        a=x,b=y;
        c.p[0]=1;
    }
    int la=a.len,lb=b.len,lc=max(la,lb);
    int f=0;

    for(int i=1;i<=lc;++i){
        if(a.p[i]<b.p[i]){
            a.p[i]+=10;
            a.p[i+1]--;
        }
        c.p[i]=a.p[i]-b.p[i];
    }
    while(lc>1 && c.p[lc]==0)--lc;
    c.len=lc;
    return c;
}
HP operator *(const HP &a,const HP &b){
    HP c;
    c.clear1();
    int la=a.len,lb=b.len,lc=la+lb;
    for(int i=1;i<=la;++i){
        int x=0;
        for(int j=1;j<=lb;++j){
            c.p[i+j-1]+=a.p[i]*b.p[j]+x;
            x=c.p[i+j-1]/10;
            c.p[i+j-1]%=10;
        }
        c.p[i+lb]=x;
    }
    while(lc>1 && c.p[lc]==0)--lc;
    c.len=lc;
    int tmp;
    if(a.p[0]==-1 && b.p[0]==-1)tmp=1;
    else if(a.p[0]>=0 && b.p[0]>=0)tmp=1;
    else tmp=-1;
    c.p[0]=tmp;
    return c;
}
HP operator /=(const HP &a,int b){
    HP c;
    c.clear1();
    int la=a.len,f=0,lc=la;
    for(int i=la;i>=1;--i){
        c.p[i]=(f*10+a.p[i])/b;
        f=(f*10+a.p[i])%b;
    }
    while(lc>1 && c.p[lc]==0)--lc;
    c.len=lc;
    return c;
}

HP operator /(const HP &x,const HP &y){
    HP c,a=x,b=y;
    c.clear1();
    int la=a.len,lb=b.len,lc=la-lb+1;
    for(int i=lc;i>=1;--i){
        HP e;
        e.clear1();
        for(int k=1;k<=lb;++k){
            e.p[k+i-1]=b.p[k];
        }
        e.len=i+lb-1;
        while(cmp(a,e)>=0)c.p[i]++,a=a-e;
    }
    while(lc>1 && c.p[lc]==0)--lc;
    c.len=lc;
    return c;
}
HP kp(HP x,int p){
    if(p<=1)return x;
    if(p%2==0)return kp(x*x,p>>1);
    else return x*kp(x*x,p>>1);
}
HP dp(int x){
    memset(f,0,sizeof f);
    for(int i=1;i<=m;++i)tmp[i]=a[x][i];
    HP two;
    two.clear1();
    two.len=1,two.p[1]=2;
    for(int i=1;i<=m;++i){
        f[i][i]=tmp[i]*two;
    }
    for(int l=2;l<=m;++l){
        for(int b=1;b+l-1<=m;++b){
            int e=b+l-1;
            f[b][e]=max1(f[b][e],two*f[b][e-1]+two*tmp[e]);
            f[b][e]=max1(f[b][e],two*f[b+1][e]+two*tmp[b]);
        }
    }
    return f[1][m];
}
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            a[i][j].read1();
        }
    }
    ans.clear1();

    for(int i=1;i<=n;++i){
        tp=dp(i);
        //write1(tmp);
        //putchar('\n');
        ans=ans+tp;
    }
    ans.write1();
    return 0; 
}
/*
5 5
0 0 0 0 0
0 0 0 0 1
876 1 566 920 598
259 945 123 659 997
176 478 293 464 278
2 3
1 5 2
3 4 2
2 4
1 4 2 3
1 4 3 2
*/

朴素高精度

struct HP{
    int p[N],len;
    void clear1(){
        memset(p,0,sizeof p);
        len=1;
        return;
    }
    void read1(){
        memset(p,0,sizeof p);
        len=1;
        p[0]=1;
        char ch=getchar();
        while(ch>'9' || ch<'0'){
            if(ch=='-')p[0]=-1;
            ch=getchar();
        }
        while(ch<='9' && ch>='0'){
            p[++len]=ch-'0';
            ch=getchar();
        }
        for(int i=1;i<=len/2;++i){
            swap(p[i],p[len-i+1]);
        }
    }
    void write1(){
        if(p[0]==-1)putchar('-');
        for(int i=len;i>=1;--i){
            putchar(p[i]+'0');
        }
        putchar('\n');
    }
};
HP operator +(const HP &a,const HP &b){
    //if(a.p[0]==-1 || b.p[0]==-1)return a-b;
    HP c;
    c.clear1();
    int la=a.len,lb=b.len,lc=max(la,lb);
    int f=0;
    for(int i=1;i<=lc;++i){
        c.p[i]=a.p[i]+b.p[i]+f;
        f=c.p[i]/10;
        c.p[i]%=10;
    }
    if(f)c.p[++lc]=f;
    c.len=lc;
    return c;
}
int cmp(const HP &a,const HP &b){
    //cout<<a.len<<" "<<b.len<<endl;
    if(a.len<b.len)return -1;
    if(a.len>b.len)return 1;
    for(int i=a.len;i>=1;--i){
        if(a.p[i]<b.p[i])return -1;
        if(a.p[i]>b.p[i])return 1;
    }
    return 0;
}
HP max1(const HP &a,const HP &b){
    int res=cmp(a,b);
    if(res>=0)return a;
    else return b;
}
HP operator -(const HP &x,const HP &y){
    HP c,a,b;
    c.clear1();
    if(cmp(x,y)==-1){
        a=y,b=x;
        c.p[0]=-1;  
    }else{
        a=x,b=y;
        c.p[0]=1;
    }
    int la=a.len,lb=b.len,lc=max(la,lb);
    int f=0;

    for(int i=1;i<=lc;++i){
        if(a.p[i]<b.p[i]){
            a.p[i]+=10;
            a.p[i+1]--;
        }
        c.p[i]=a.p[i]-b.p[i];
    }
    while(lc>1 && c.p[lc]==0)--lc;
    c.len=lc;
    return c;
}
HP operator *(const HP &a,const HP &b){
    HP c;
    c.clear1();
    int la=a.len,lb=b.len,lc=la+lb;
    for(int i=1;i<=la;++i){
        int x=0;
        for(int j=1;j<=lb;++j){
            c.p[i+j-1]+=a.p[i]*b.p[j]+x;
            x=c.p[i+j-1]/10;
            c.p[i+j-1]%=10;
        }
        c.p[i+lb]=x;
    }
    while(lc>1 && c.p[lc]==0)--lc;
    c.len=lc;
    int tmp;
    if(a.p[0]==-1 && b.p[0]==-1)tmp=1;
    else if(a.p[0]>=0 && b.p[0]>=0)tmp=1;
    else tmp=-1;
    c.p[0]=tmp;
    return c;
}
HP operator /=(const HP &a,int b){
    HP c;
    c.clear1();
    int la=a.len,f=0,lc=la;
    for(int i=la;i>=1;--i){
        c.p[i]=(f*10+a.p[i])/b;
        f=(f*10+a.p[i])%b;
    }
    while(lc>1 && c.p[lc]==0)--lc;
    c.len=lc;
    return c;
}

HP operator /(const HP &x,const HP &y){
    HP c,a=x,b=y;
    c.clear1();
    int la=a.len,lb=b.len,lc=la-lb+1;
    for(int i=lc;i>=1;--i){
        HP e;
        e.clear1();
        for(int k=1;k<=lb;++k){
            e.p[k+i-1]=b.p[k];
        }
        e.len=i+lb-1;
        while(cmp(a,e)>=0)c.p[i]++,a=a-e;
    }
    while(lc>1 && c.p[lc]==0)--lc;
    c.len=lc;
    return c;
}
记得常清零，少用局部变量，不然会出现初始值不为零的情况。

压缩高精度

const int M=1000+5,base=1e8;
int n;
struct BigInt{
    int sum[21];
    void operator += (const BigInt &x){
        sum[0]=max(sum[0],x.sum[0]);
        for(int i=1; i<=sum[0]; i++){
            sum[i]+=x.sum[i];
            if(sum[i]>=base) sum[i+1]++,sum[i]-=base;
        }
        if(sum[sum[0]+1]>0) sum[0]++;
    }
    void operator *= (const BigInt &x){
        long long A[21]={};
        for(int i=1; i<=sum[0]; i++){
            for(int j=1; j<=x.sum[0]; j++){
                A[i+j-1]+=1ll*sum[i]*x.sum[j];
            }
        }
        for(int i=1; i<=sum[0]+x.sum[0]; i++){
            A[i+1]+=A[i]/base; A[i]%=base; sum[i]=A[i];
        }
        if(A[sum[0]+x.sum[0]]) sum[0]=sum[0]+x.sum[0];
        else sum[0]=sum[0]+x.sum[0]-1;
    }
    void Print(){
        printf("%d",sum[sum[0]]);
        for(int i=sum[0]-1; i>0; i--){
            printf("%08d",sum[i]);
        }
    }
}