CSU 1720 How to Get 2^n (大数+hash)
发布时间:2021-03-18 11:47:53 所属栏目:大数据 来源:网络整理
导读:题意:给你10W个数字,每个数都是大数,范围是1到10^30,然后问你有多少种方法,每次选取两个数,两个数的和是2的幂次 题解:10的30次大约是2的100次,所以先预处理2的102次,然后就是每次输入一个大数,枚举2的幂次去减它,然后去map里找有多少个解,其实是
题意:给你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 ****************************************************************/ (编辑:52站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |