Knapsack Cryptosystem（状压dp）

题目描述

Amy asks Mr. B problem E. Please help Mr. B to solve the following problem.

There are n people, who don't know each other at the beginning.

There are m turns. In each turn, 2 of them will make friends with each other.

The friend relation is mutual and transitive.

If A is a friend of B, then B is also a friend of A.

For example, if A is a friend of B, B is a friend of C, then A and C are friends.

At the beginning and after each turn, please calculate the number of ways to select four people from, such that any two of these four are not friends.

输入描述:

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.

示例1

输入

复制

输出

复制

示例2

输入

复制

100000 0

输出

复制

4166416671249975000

说明

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 }