发现至少有 \(\frac{S}{5}\) 个 \(1\)，所以考虑维护 \((k,T-k)\) 的对数，然后二进制拆分+维护区间连续段背包 dp 即可。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define lowbit(x) x&(-x)
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef pair<int,int> pir;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=x*10+(c^48); c=getchar();}
return x*f;
}
const int inf=1e18,N=2e5+5;
int n,S;
int a[N],cnt[N],op,ans;
vector<pir> dp[N*2];
inline int P(int x){return x+n;}
inline void merge(vector<pir> &x,int L,int R){
if(x.empty()){x.push_back(mkp(L,R));return ;}
vector<pir> y; y.clear();
for(auto [l,r]:x){
if(r<L||R<l){y.push_back(mkp(l,r));continue;}
L=min(L,l),R=max(R,r);
}
y.push_back(mkp(L,R));
swap(x,y);
}
inline void upd(int val,int siz){
if(val>0){
for(int i=S;i>=-op;i--){
if(dp[P(i)].empty()) continue;
for(auto [l,r]:dp[P(i)])
merge(dp[P(i+val)],l+siz,r+siz);
}
}
else{
for(int i=-op;i<=S;i++){
if(dp[P(i)].empty()) continue;
for(auto [l,r]:dp[P(i)])
merge(dp[P(i+val)],l+siz,r+siz);
}
}
}
signed main(){
n=read(),S=read();
for(int i=1;i<=n;i++) a[i]=read(),cnt[a[i]]++;
dp[P(0)].push_back(mkp(0,cnt[1]));
op=cnt[0];
for(int i=0;i<=S;i++){
if(!cnt[i]||i==1) continue;
for(int w=1;w<=cnt[i];w<<=1){
int val=i*w-w;
cnt[i]-=w;
upd(val,w);
}
if(cnt[i]) upd(cnt[i]*i-cnt[i],cnt[i]);
}
for(int i=-op;i<=S;i++){
for(auto [l,r]:dp[P(i)]) ans+=(r-l+1);
}
cout<<ans<<'\n';
}