题意&思路

本题实际上是求给出的数组的子集有多少个和不超过 $m$。

注意到 $n\le40$，如果暴力枚举 $2^n$ 铁定超时。

我们可以使用双向搜索优化。先对 $1\sim\frac{n}{2}$ 枚举得到 $b$，再对 $\frac{n}{2}\sim n$ 枚举得到 $c$，然后对 $b$ 和 $c$ 分别排序，再用双指针 $O(n)$ 地算出有多少对满足条件，如果 $b$ 的某一项和 $c$ 的某一项和不超过 $m$ 就视为合法的一对。

整体时间复杂度是 $O(2^{\frac{n}{2}})$ 级别的，不会超时。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=45,M=1100000; // 1100000>2^20
ll n,m,a[N],b[M],c[M],t1,t2,k,ans;
void dfs1(ll x,ll cnt){
    if(x==k+1){
        b[++t1]=cnt;
        return;
    }
    dfs1(x+1,cnt); // 不选x
    if(cnt+a[x]<=m)
        dfs1(x+1,cnt+a[x]); // 选x
}
void dfs2(ll x,ll cnt){
    if(x==n+1){
        c[++t2]=cnt;
        return;
    }
    dfs2(x+1,cnt); // 不选x
    if(cnt+a[x]<=m)
        dfs2(x+1,cnt+a[x]); // 选x
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    k=n/2;
    dfs1(1,0),dfs2(k+1,0);
    sort(b+1,b+1+t1),sort(c+1,c+1+t2);
    ll j=t2;
    for(ll i=1;i<=t1;i++){
        while(j&&b[i]+c[j]>m)
            j--;
        ans+=j;
    }
    printf("%lld",ans);
    return 0;
}