题目描述
The first line contains two integers, n and m (n <= 100000, m <= 200000), which are the number of people, and the number of turns.
In the following m lines, the i-th line contains two integers x and y ( 1 <= x <= n, 1 <= y <= n, x ≠ y), which means the x-th person and the y-th person make friends in the i-th turn.
The x-th person and y-th person might make friends in several turns.
Output m+1 lines, each line contains an integer, which is the number of quadruples.
Output at the beginning and after each turn, so there are m+1 lines.
Don‘t use int.
解题报告：这个题目在一开始看起来就是一个背包，但是呢，背包的容量太大了，数组没有办法去存储，然后呢可以考虑一下状压，因为呢n是小于等于36的，
显然是没有办法直接去状压的，所以就可以分段折半去状压，这样的复杂度就能跳崖式减小，需要开个map去存储，后半段求解过程中就去在map中查询，然后
每次就去判断，需要注意的就是需要开设两个数组去存储，只用一个的话得不到想要的结果。
ac代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #include<map> 7 using namespace std; 8 typedef long long ll; 9 10 const int maxn = 1e6+1000; 11 12 ll num1[maxn]; 13 ll num2[maxn]; 14 ll sum[maxn]; 15 ll sum2[maxn]; 16 int n; 17 ll s; 18 map<ll ,int> mp; 19 int main() 20 { 21 cin>>n>>s; 22 for(int i=1;i<=n;i++) 23 cin>>num1[i]; 24 int mid=n/2; 25 for(int i=1;i<=mid;i++) 26 num2[i-1]=num1[i]; 27 for(int i=0;i<(1<<mid);i++) 28 { 29 for(int j=0;j<mid;j++) 30 { 31 if(i&(1<<j)) 32 sum[i]+=num2[j]; 33 } 34 mp[sum[i]]=i; 35 } 36 int mid2=n-mid; 37 for(int i=mid+1;i<=n;i++) 38 num2[i-mid-1]=num1[i]; 39 for(int i=0;i<(1<<mid2);i++) 40 { 41 for(int j=0;j<mid2;j++) 42 { 43 if(i&(1<<j)) 44 sum2[i]+=num2[j]; 45 } 46 if(mp.count(s-sum2[i])) 47 { 48 int tmp=mp[s-sum2[i]]; 49 for(int j=0;j<mid;j++) 50 { 51 if(tmp&(1<<j)) 52 cout<<1; 53 else 54 cout<<0; 55 } 56 for(int j=0;j<mid2;j++) 57 { 58 if(i&(1<<j)) 59 cout<<1; 60 else 61 cout<<0; 62 } 63 cout<<endl; 64 } 65 } 66 }
原文：https://www.cnblogs.com/Spring-Onion/p/11360771.html