神人题解，看不懂一点 非正解复杂度😡🐕‍🦺🐣暴力拿下

#define LOCAL
#include<bits/stdc++.h>
#include<unistd.h>
#include<bits/extc++.h>
//#define getchar my_gechar
#define ll long long
#define lll __int128
#define db double
#define ldb long double
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int> 
#define vec Point
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
// #define max(a,b) ((a)<(b)?(b):(a))
// #define min(a,b) ((a)<(b)?(a):(b))
#define vi vector<int> 
#define vl vector<ll>
#define lowbit(x) (x)&(-x)
//#define sort stable_sort
using namespace std;
using namespace __gnu_pbds;
char buffer[32769];
unsigned li = 0;
inline char my_gechar(){
    if(buffer[li] == '\0') buffer[read(0, buffer, 32768)] = '\0',li = 0;
    return buffer[li++];
}
namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;

            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
                  inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline int read(double &x){return scanf("%lf",&x);}
            inline int read(long double &x){return scanf("%Lf",&x);}
            inline void dwrite(const double &x,int y=6,bool flag=1){printf("%.*lf",y,x),flag?putchar(' '):putchar(' ');}
            inline void dwrite(const long double &x,int y=6,bool flag=1){printf("%.*Lf",y,x),flag?putchar(' '):putchar(' ');}
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const char *x){while(*x)putchar(*(x++));}
            inline void read(string &x){char ch[1000005]={};read(ch),x=ch;}
            inline void write(const string &x){int len=x.length();for(int i=0;i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>
            inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar(' ');}
            inline __int128 read(){static __int128 x;return read(x);}
            template<typename type>
            inline type put(type x,bool flag=1){write(x),flag?putchar(' '):putchar(' ');return x;}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;
struct Point{
    int x,y;
    Point operator +(const Point& b)const{return {x+b.x,y+b.y};}
    Point operator -(const Point& b)const{return {x-b.x,y-b.y};}
    bool operator <(const Point& b)const{
        if(x!=b.x)return x<b.x;
        return y<b.y;
    }
};
const int N=1e5+5;
const int M=1e6+5;
const int inf=1e9+5;
const int mod=1e9+7;
const int bit=50;
//mt19937 sj(chrono::steady_clock::now().time_since_epoch().count());
int B=705;
int n;
int a[50];
int sum_l[1<<21],sum_r[1<<21],temp[1<<21];
int l[1<<21],r[1<<21];
inline void solve(){
    read(n);
    for(int i=1;i<=n;++i) read(a[i]);
    int n1=n>>1;
    int n2=n-n1;
    int t1=n1,t2=n2;
    n1=1<<n1;
    n2=1<<n2;
    for(int i=0;i<n1;++i){
        for(int j=0;j<t1;++j) if(i>>j&1) sum_l[i]+=a[j+1];
    }
    for(int i=0;i<n2;++i){
        for(int j=0;j<t2;++j) if(i>>j&1) sum_r[i]+=a[j+t1+1];
    }
    // sort(sum_l,sum_l+n1);
    // sort(sum_r,sum_r+n2);
    ll ans=0;
    int base=1;
    int sum=0;
    for(int i=1;i<=n;++i){
        sum+=a[i];
    }
    int p,l1,l2,r1,r2;
    for(;1ll*base*10<=1000000000&&base<=sum;base*=10){
        ;
    }
    base/=10;
    for(int i=0;i<n1;++i) temp[i]=sum_l[i];
    int L,R;
    sum_l[n1]=inf;
    for(;base>=1;base/=10){
        p=(base<<3)+(base<<1);
        l1=base<<2;
        r1=l1+base;
        l2=l1+(base<<3)+(base<<1);
        r2=l2+base;
        for(int i=0;i<n1;++i) sum_l[i]%=p;
        sort(sum_l,sum_l+n1);
        for(int i=0;i<n2;++i) sum_r[i]%=p;
        sort(sum_r,sum_r+n2);
        L=n1;
        for(int i=0;i<n2;++i){
            while(L>0&&sum_r[i]+sum_l[L-1]>=l1) --L; 
            l[i]=L;
        }
        R=-1;
        for(int i=n2-1;i>=0;--i){
            while(R+1<n2&&sum_r[i]+sum_l[R+1]<r1) ++R;
            r[i]=R;
        }
        for(int i=0;i<n2;++i){
            ans+=r[i]-l[i]+1;
        }
        L=n1;
        for(int i=0;i<n2;++i){
            while(L>0&&sum_r[i]+sum_l[L-1]>=l2) --L; 
            l[i]=L;
        }
        R=-1;
        for(int i=n2-1;i>=0;--i){
            while(R+1<n2&&sum_r[i]+sum_l[R+1]<r2) ++R;
            r[i]=R;
        }
        for(int i=0;i<n2;++i){
            ans+=r[i]-l[i]+1;
        }
    }
    write(ans);
}

signed main()
{   
    int _=1;
    while(_--) solve();
    return (0-0);
}