小马哥有 \(n\) 杯盐水，第 \(i\) 杯有 \(a_i\)单位的盐和 \(b_i\)单位的水。小马哥很无聊，于是他想知道有多少种这 \(n\) 杯盐水的非空子集，倒在一起之后盐和水的比是 \(\frac{x}{y}\)，范围\(2<n<35\)

这道题比赛没A出来，要是A了就能两个人分900块辣

//隔了一天才突然想到,我太菜了

折半枚举过程如下

分两个桶A,B,分别装前一半杯子的子集和后一半杯子的子集

先暴力枚举A桶所有组合，装入一个排好序的vec，这部分时间复杂度是\(O(2^{n/2}log_22^{n/2})\)

再暴力枚举B桶的方案，二分找出能和A匹配的方案个数，这部分时间复杂度也是\(O(2^{n/2}log_22^{n/2})\)

最后统计A、B自身符合条件的方案就行了

至于如何二分，可以考虑假设A的某个集合本身不能匹配，

设该状态盐总和为\(a\)，水总和为\(b\)，那么就有\(ay≠bx\)

设B桶枚举的集合中盐总和为\(c\)，水总和为\(d\)，那么有\((a+c)y=(b+d)x\)

简单移项后得出\(ay-bx=dx-cy\)

按这条式子就能二分了

PS.实现是dalao写的,自己写的翻车了,思路没错..

#include
    
     #include
     
      #include
      
       using namespace std;const int maxn = 40;const int maxm = (1<<18)+5;int elema[maxn],elemb[maxn];int zka[maxm],zkb[maxm];void ZHANGKAI(int val[],int elem[],int size){    val[0] = 0;    for(int i = 1;i<=size;i++)    {        int st = 1<<(i-1);        int ed = 1<
       
        >kase;    for(int i = 0;i
        
         >n>>x>>y;        int half = n>>1;        for(int i = 1;i<=half;i++)        {            cin>>a>>b;            elema[i] = y*a-x*b;        }                for(int i = half+1;i<=n;i++)        {            cin>>a>>b;            // elemb[i-half] = elema[i];            elemb[i-half] = x*b-y*a;        }        ZHANGKAI(zka,elema,half);        ZHANGKAI(zkb,elemb,n-half);        int sizeb = (1<<(n-half));        sort(zkb+1,zkb+sizeb);        long long ans = 0;        int end = 1<