题意：给你一个集合，求它的所有子集的子集和中数字4出现了多少次
例如
4
4 4 44 44
中4(1)，4(2)，44(3)，44(4)，48(1,3)，48(1,4)，48(2,3)，48(2,4)，总共有10个数字4
思路：
明显数据范围就是要拆开来做，先将子集尽可能平均分
这样就有两个大小不超过220的子集和集合。
考虑集合里所有数字的每一位对答案的贡献
只有两种可能，一种是当前位数两位相加没有进位，一种是当前位数两位相加有进位
分别统计就是答案
而如果将当前位之后的那一部分数字从小到大有序排列好，就可以用两个指针分别从两边去扫
然而直接排序会超时
所以考虑类似于归并的思想，转移时候将当前位拆开按顺序重新丢入大集合里
就可以保证答案的正确性了
注意卡常
1 #include<bits/stdc++.h> 2 #define pb push_back 3 using namespace std; 4 int read(){ 5 int x=0,f=1;char c=getchar(); 6 for(;!isdigit(c);c=getchar())if(c==‘-‘)f=-1; 7 for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48); 8 return x*f; 9 } 10 typedef long long ll; 11 struct data{ll fi,se;}; 12 data mp(ll a,ll b){ 13 data ret; 14 ret.fi=a;ret.se=b; 15 return ret; 16 } 17 typedef data pll; 18 int n,li[50]; 19 vector<pll> X,Y,A[10],B[10]; 20 21 void get_X(int dep,ll sum){ 22 if(dep>(n/2)){X.pb(mp(sum,0));return;} 23 get_X(dep+1,sum);get_X(dep+1,sum+li[dep]); 24 } 25 void get_Y(int dep,ll sum){ 26 if(dep>n){Y.pb(mp(sum,0));return;} 27 get_Y(dep+1,sum);get_Y(dep+1,sum+li[dep]); 28 } 29 30 ll get0(vector<pll> &a,vector<pll> &b,ll Base){ 31 ll ret=0;int p=b.size()-1; 32 for(int i=0;i<a.size();ret+=p+1,++i) 33 for(;p>=0&&b[p].se+a[i].se>=Base;--p); 34 return ret; 35 } 36 ll get1(vector<pll> &a,vector<pll> &b,ll Base){ 37 ll ret=0;int p=0; 38 for(int i=a.size()-1;~i;ret+=b.size()-p,--i) 39 for(;p<b.size()&&b[p].se+a[i].se<Base;++p); 40 return ret; 41 } 42 43 void solve(){ 44 X.clear();Y.clear(); 45 46 n=read(); 47 for(int i=1;i<=n;++i)li[i]=read(); 48 get_X(1,0);get_Y(n/2+1,0); 49 //get two set 50 ll ans=0,Base=1,tmp; 51 pll x,y,a,b; 52 for(int i=0;i<11;++i,Base*=10){ 53 for(int j=0;j<10;++j)A[j].clear(),B[j].clear(); 54 55 for(int j=0;j<X.size();++j) 56 x=X[j],A[x.fi%10].pb(mp(x.fi/10,x.se)); 57 for(int j=0;j<Y.size();++j) 58 y=Y[j],B[y.fi%10].pb(mp(y.fi/10,y.se)); 59 //get this digit 60 for(int j=0,k;j<10;++j){ 61 k=(14-j)%10; 62 ans+=get0(A[j],B[k],Base); 63 k=(13-j)%10; 64 ans+=get1(A[j],B[k],Base); 65 } 66 //Calc the ans 67 for(int j=0,now=0;j<10;++j){ 68 tmp=Base*j; 69 for(int k=0;k<A[j].size();++k) 70 a=A[j][k],X[now++]=mp(a.fi,a.se+tmp); 71 } 72 for(int j=0,now=0;j<10;++j){ 73 tmp=Base*j; 74 for(int k=0;k<B[j].size();++k) 75 b=B[j][k],Y[now++]=mp(b.fi,b.se+tmp); 76 } 77 } 78 printf("%lld\n",ans); 79 } 80 81 int main(){ 82 for(int T=read()+1;--T;)solve(); 83 return 0; 84 }