HDU 6682 Make Rounddog Happy

題意：給你一個集合，求它的所有子集的子集和中數字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

?

思路：

明顯數據范圍就是要拆開來做，先將子集盡可能平均分

這樣就有兩個大小不超過2²⁰的子集和集合。

考慮集合里所有數字的每一位對答案的貢獻

只有兩種可能，一種是當前位數兩位相加沒有進位，一種是當前位數兩位相加有進位

分別統計就是答案

而如果將當前位之后的那一部分數字從小到大有序排列好，就可以用兩個指針分別從兩邊去掃

然而直接排序會超時

所以考慮類似于歸并的思想，轉移時候將當前位拆開按順序重新丟入大集合里

就可以保證答案的正確性了

注意卡常

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
typedef long long ll;
struct data{ll fi,se;};
data mp(ll a,ll b){
    data ret;
    ret.fi=a;ret.se=b;
    return ret;
}
typedef data pll;
int n,li[50];
vector<pll> X,Y,A[10],B[10];

void get_X(int dep,ll sum){
    if(dep>(n/2)){X.pb(mp(sum,0));return;}
    get_X(dep+1,sum);get_X(dep+1,sum+li[dep]);
}
void get_Y(int dep,ll sum){
    if(dep>n){Y.pb(mp(sum,0));return;}
    get_Y(dep+1,sum);get_Y(dep+1,sum+li[dep]);
}

ll get0(vector<pll> &a,vector<pll> &b,ll Base){
    ll ret=0;int p=b.size()-1;
    for(int i=0;i<a.size();ret+=p+1,++i)
        for(;p>=0&&b[p].se+a[i].se>=Base;--p);
    return ret;
}
ll get1(vector<pll> &a,vector<pll> &b,ll Base){
    ll ret=0;int p=0;
    for(int i=a.size()-1;~i;ret+=b.size()-p,--i)
        for(;p<b.size()&&b[p].se+a[i].se<Base;++p);
    return ret;
}

void solve(){
    X.clear();Y.clear();
    
    n=read();
    for(int i=1;i<=n;++i)li[i]=read();
    get_X(1,0);get_Y(n/2+1,0);
    //get two set
    ll ans=0,Base=1,tmp;
    pll x,y,a,b; 
    for(int i=0;i<11;++i,Base*=10){
        for(int j=0;j<10;++j)A[j].clear(),B[j].clear();
        
        for(int j=0;j<X.size();++j)
            x=X[j],A[x.fi%10].pb(mp(x.fi/10,x.se));
        for(int j=0;j<Y.size();++j)
            y=Y[j],B[y.fi%10].pb(mp(y.fi/10,y.se));
        //get this digit
        for(int j=0,k;j<10;++j){
            k=(14-j)%10;
            ans+=get0(A[j],B[k],Base);
            k=(13-j)%10;
            ans+=get1(A[j],B[k],Base);
        }
        //Calc the ans
        for(int j=0,now=0;j<10;++j){
            tmp=Base*j;
            for(int k=0;k<A[j].size();++k)
                a=A[j][k],X[now++]=mp(a.fi,a.se+tmp);
        }
        for(int j=0,now=0;j<10;++j){
            tmp=Base*j;
            for(int k=0;k<B[j].size();++k)
                b=B[j][k],Y[now++]=mp(b.fi,b.se+tmp);
        }
    }
    printf("%lld\n",ans);
}

int main(){
    for(int T=read()+1;--T;)solve();
    return 0;
}

?