SRM 622 div2 1000

给一有重复数字集合, 求满足以下性质的所有子集(可全集不可空集):
所有数字和大于数字积, 1<=n<=1000

观察1
..:
若xy<x+y则xy-x-y<0
即xy-x-y+1<1即(x-1)(y-1)<1, 可见x, y中至少有1
..:
若xyz<x+y+z则xyz-x-y-z<0
即xyz-xy-yz-zx+x+y+z-1+xy+yz+xz-2x-2y-2z+1<0
也(x-1)(y-1)(z-1)+(x-1)(y-1)+(y-1)(z-1)+(x-1)(z-1)<2, 可见x, y, z中至少有1
..:
猜测推广至n

观察2
..:
根据观察1可见复杂度并不是n的全子集, 至于是什么不会证QAQ:..

所以
..:
先求出1的个数, 然后枚举非1元素的子集, 看是否满足要求
排序后可以剪枝, 就是当发现已经不满足就没有必要继续枚举了

写出代码
..:

#include <bits/stdc++.h>
using namespace std;

int n, o, r, t;
int v[1001];
int m[1001];
int s[1001];
inline void dodo(int x, int c) {
    int a=0, b=1;
    for (int i=0; i<c; i++) a+=s[i], b*=s[i];
    if (b-a<=o)
        r+=o-(b-a);
    else
        return;
    for (int i=x; i<t; i++) if (v[i]) {
        s[c]=m[i];
        v[i]--;
        dodo(i, c+1);
        v[i]++;
    }
}
inline void push(int x) {
    for (int i=0; i<t; i++) if (m[i]==x) {
        v[i]++;
        return;
    }
    m[t]=x;
    v[t]++;
    t++;
}
class Subsets {
public:
    int findSubset(vector<int> N) {
        n=N.size();
        sort(N.begin(), N.end());
        for ( ; N[o]==1 && o<n; o++) ;
        for (int i=o; i<n; i++)
            push(N[i]);
        dodo(0, 0);
        printf("%d %d\n", n, o);
        return r;
    }
};