思路比较巧妙。
首先排序。
考虑目前维护出 \(a_{1 \sim i}\) 不能表示的数的集合 \(S\)。
考虑如何加入 \(a_{i+1}\)。
如果当前 \(<a_i\) 的数足够了，直接输出（因为这些数将会一直留在 \(S\) 中）。
记 \(sum=\sum\limits_{j=1}^{i}a_j\)。
\(a_{i+1}>sum\)
\[S'=S\cup [sum+1,a_{i+1}-1] \cup \{x+a_{i+1}|x\in S\}
\]
-
若 \(|S\cup [sum+1,a_{i+1}-1]|\ge k\)，则直接输出了。
-
若 \(|S\cup [sum+1,a_{i+1}-1]|< k\)
-
\[|\{x+a_{i+1}|x\in S\}|=|S| \]
-
\[\Longrightarrow |S'|<|S|+k \]
-
\(a_{i+1}\le sum\)
\[S'=(S\cap [1,a_{i+1}-1])\cup\{x+a_{i+1}|x\in S \and (x+a_{i+1}\in S\or x+a_{i+1}>sum)\}
\]
-
若 \(|S\cap [1,a_{i+1}-1]|\ge k\)，直接输出。
-
若 \(|S\cap [1,a_{i+1}-1]|<k\)
-
\[|\{x+a_{i+1}|x\in S \and (x+a_{i+1}\in S\or x+a_{i+1}>sum)\}|\le |S| \]
-
\[\Longrightarrow |S'| < |S|+k \]
-
最后一步
所以每次增加的个数 \(<k\)，总个数在 \(O(nk)\) 级别。
所以复杂度可以做到 \(O(nk\log(nk))\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=65;
const ll INF=1e18;
int n,m;
ll a[N];
set<ll>S,T;
void print(){
if((int)S.size()<m)return;
for(ll x:S){
cout<<x<<"\n "[--m>0];
if(!m)break;
}
exit(0);
}
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n),a[++n]=INF;
ll sum=0;
for(int i=1;i<=n;i++){
if(a[i]<=sum){
S.swap(T),S.clear();
for(ll x:T){
if(x<a[i])S.insert(x);
print();
}
for(ll x:T){
if(x>a[i]&&T.count(x-a[i]))S.insert(x);
if(x+a[i]>sum)S.insert(x+a[i]);
}
}else{
S.swap(T),S=T;
for(ll j=sum+1;j<a[i];j++){
S.insert(j);
print();
}
for(ll x:T)S.insert(x+a[i]);
}
sum+=a[i];
}
return 0;
}