CSU 1720 How to Get 2^n （大数+hash）

题意：给你10W个数字，每个数都是大数，范围是1到10^30，然后问你有多少种方法，每次选取两个数，两个数的和是2的幂次

题解：10的30次大约是2的100次，所以先预处理2的102次，然后就是每次输入一个大数，枚举2的幂次去减它，然后去map里找有多少个解，其实是个很简单的思路，但是我却一直写炸，主要是大数的模板太差，会T，加上我智商下线，开了很大的数组去存输入的内容，结果实力T。

其实一边输入，然后转化为大数，然后枚举2的幂次，相减，然后hash，去map里面查，然后累计求和，然后把输入hash，放进map里，这样就好了

问qwb神犇要了新的姿势的大数模板otz，感觉十分之屌，跑得飞快

#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")
 
using namespace std;
#define   MAX           100005
//#define   MAXN          500005
#define   maxnode       105
#define   sigma_size    2
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   lrt           rt<<1
#define   rrt           rt<<1|1
#define   middle        int m=(r+l)>>1
#define   LL            long long
#define   ull           unsigned long long
#define   mem(x,v)      memset(x,v,sizeof(x))
#define   lowbit(x)     (x&-x)
#define   pii           pair<int,int>
#define   bits(a)       __builtin_popcount(a)
#define   mk            make_pair
#define   limit         10000
 
//const int    prime = 999983;
const int    INF   = 0x3f3f3f3f;
const LL     INFF  = 0x3f3f;
const double pi    = acos(-1.0);
const double inf   = 1e18;
const double eps   = 1e-9;
const LL     mod   = 1e9+7;
const ull    mx    = 1e9+7;
 
/*****************************************************/
inline void RI(int &x) {
      char c;
      while((c=getchar())<'0' || c>'9');
      x=c-'0';
      while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';
}
/*****************************************************/
 
const int MX = 10;//一共可以表示长度MX*DLEN的
const int maxn = 9999;
const int DLEN = 4;//一个int里面放多少个数字
 
char ret[105];
class Big {
public:
    int a[MX],len;
    Big(const int b = 0) {
        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;
    }
    Big(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;
        }
    }
    Big operator/(const int &b)const {
        Big ret;
        int i,down = 0;
        for(int 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;
    }
    bool operator>(const Big &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;
    }
    Big operator+(const Big &T)const {
        Big 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;
    }
    Big operator-(const Big &T)const {
        int i,j,big;
        bool flag;
        Big 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[t1.len - 1] == 0 && t1.len > 1) {
            t1.len--;
            big--;
        }
        if(flag) t1.a[big - 1] = 0 - t1.a[big - 1];
        return t1;
    }
    int operator%(const int &b)const {
        int i,d = 0;
        for(int i = len - 1; i >= 0; i--) {
            d = ((d * (maxn + 1)) % b + a[i]) % b;
        }
        return d;
    }
    Big operator*(const Big &T) const {
        Big ret;
        int i,up,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;
    }
    ull print() {
        ull ret=0;
        for(int i=len-1;i>=0;i--) ret=ret*mx+a[i];
        return ret;
    }
}pow2[105],ss;
map<ull,int> ma;
char s[105];
void init(){
    pow2[0]=1;
    for(int i=1;i<=103;i++) pow2[i]=pow2[i-1]*2;
}
int main(){
    //freopen("test.txt","r",stdin);
    int t;
    cin>>t;
    init();
    while(t--){
        int n;
        cin>>n;
        ma.clear();
        LL ans=0;
        for(int i=0;i<n;i++){
            scanf("%s",s);
            int len;
            ss=s;
            for(int j=103;j>=1;j--){
                if(pow2[j]>ss){
                    Big cnt=pow2[j]-ss;
                    ull temp=cnt.print();
                    if(ma.count(temp)) ans+=ma[temp];
                }
            }
            ull tmp=ss.print();
            if(!ma.count(tmp)) ma[tmp]=0;
            ma[tmp]++;
            //cout<<ma[ss[i]]<<" "<<ss[i]<<endl;
        }
        cout<<ans<<endl;
    }
    return 0;
}
 
/**************************************************************
    Problem: 1720
    User: 1403mashaonan
    Language: C++
    Result: Accepted
    Time:5640 ms
    Memory:4272 kb
****************************************************************/

（编辑：核心网）

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