### PROBLEM LINK:

**Author:** Hanlin Ren

**Tester:** Jingbo Shang

**Editorialist:** Hanlin Ren

### DIFFICULTY:

hard

### PREREQUISITES:

math, combinatorics, sqrt-decomposition

### PROBLEM:

Given an undirected simple graph G=(V,E), for a subset S\subseteq V we define f(S) is the number of edges in the induced subgraph of S. Find

### QUICK EXPLANATION:

The problem actually asks you to enumerate all lists of edges of length k, and suppose these k edges occupy p vertices, the answer is added by 2^{N-p}. We only need to count how many lists occupy p=2\dots 2k vertices when k\le 3, and we do it for every p=2\dots 2k separately. Some sqrt-decomposition tricks may help.

### EXPLANATION:

##Subtask 1

We enumerate all subsets S\subseteq V and calculate f(S)^k and add them together.

Time complexity: O(M2^N).

##Subtask 2 and 4

The answer is the number of ways to choose the following things:

- a subset S of V;
- a list of edges of length k: (e_1,e_2,\dots,e_k)

such that every endpoint of every e_i is in S. To see this, if you fix S then there are exactly f(S)^k ways to choose the edge list.

To calculate the answer, let’s enumerate the list first. For a list (e_1,e_2,\dots,e_k), if a vertex v is the endpoint of some e_i, then it must be in S; otherwise it’s can be in S or out S. So the number of ways to choose S is 2^{N-p}, where p is the number of vertices that are endpoints of some e_i.

This gives an O(M^k) algorithm: we simply enumerate the edge list, calculate its p value, and add 2^{N-p} to the answer. This can pass subtask 2 and 4.

##Subtask 2

Specially, for k=1, since the graph is simple, for any edge(list of length 1), its p=2. So the answer is M\cdot 2^{N-2}.

##Subtask 3

For k=2, we need to know the number of ordered edge pairs (e_1,e_2) so their p=2,3,4 respectively.

For p=2, the answer is a_{22}=M, since the graph is simple and we have to select two identical edges.

For p=3, let’s enumerate the common vertex of e_1 and e_2, say v. Then there are d(d-1) ways to select these two edges, where d=\deg_v is the degree of the vertex. We sum up all the numbers, and the answer is a_{23}=\sum_{v\in V}\deg_v(\deg_v-1).

For p=4, the answer is a_{24}=M^2-a_{22}-a_{23}.

This subtask can be done in O(M).

##Subtask 5

(Below are some graph theory terms that’ll appear later)

For k=3, we need to know the number of edge lists (e_1,e_2,e_3) so their p=2,3,4,5,6 respectively.

For p=2, we need to pick 3 identical edges, so the answer is a_{32}=M;

For p=3, there are two cases:

- We pick two edges that has a common vertex, and duplicate one of them. There are 3a_{23} ways: a_{23} ways to pick such two edges and select one(to duplicate), and 3 ways to arrange them(112,121,211);
- We pick a triangle. we can enumerate one vertex in the triangle, say v, then the number of triangles is

We define B(v)=\sum_{(u,v)\in E}\sum_{(w,v)\in E}[(u,w)\in E], then there are tri=\sum_{v\in V}B(v) triangles.

thus a_{33}=3a_{23}+tri;

For p=4, there are three cases:

- We pick two edges that doesn’t have common vertices, and duplicate one of them. There are 3a_{24} ways;
- We pick a claw. Let’s enumerate the degree-3 vertex of the claw, say v, then there are \deg_v(\deg_v-1)(\deg_v-2) ways. The total answer is claw=\sum_{v\in V}\deg_v(\deg_v-1)(\deg_v-2).
- We pick a path of 4 vertices(P_4). Let’s enumerate the middle edge, suppose its endpoints are u and v. Then there are (\deg_u-1)(\deg_v-1) ways to pick the remaining two edges. We can rearrange the three edges in 6 ways, so the total answer is P_4=6\sum_{(u,v)\in E}(\deg_u-1)(\deg_v-1).

However every triangle is also counted 3 times, thus a_{34}=3a_{24}+claw+P_4-3\cdot tri.

For p=5, the only situation is P_2+P_3, i.e., two chains of 2 vertices and 3 vertices respectively. Let’s enumerate the midpoint of P_3, say, v. We can then enumerate v's two neighbors u and w, so the P_3 is u-v-w. How many edges could be the P_2? All edges that doesn’t have u,v,w as endpoints are eligible, so the number of valid P_2's is M-\deg_u-\deg_v-\deg_w+f(\{u,v,w\}), where f(\{u,v,w\})=[(u,v)\in E]+[(u,w)\in E]+[(v,w)\in E] is the number of edges that are counted twice in \deg_u+\deg_v+\deg_w. Notice that f(\{u,v,w\})=2+[(u,w)\in E], so the number of valid P_2's is M-\deg_u-\deg_v-\deg_w+2+[(u,w)\in E]. Thus we have

where B(v)=\sum_{(u,v)\in E}\sum_{(w,v)\in E}[(u,w)\in E] is defined above.

The rest situation p=6 is easy: we simply subtract what we calculated from M^3: a_{36}=M^3-a_{32}-a_{33}-a_{34}-a_{35}.

Everything can be solved in O(M) time, except the calculation for B(v). The time for computing B(v) is \sum_{v\in V}\deg_v^2=O(NM). That passes subtask 5.

##Subtask 6

### Author’s solution

Note that the bottleneck of the above algorithm is to calculate B. In fact, we have a simple algorithm for computing B(v) in O(M\sqrt{M}) time:

- First we can use hash tables to support the operation "check if an edge is in E" in constant time;
- Enumerate v\in V;
- If \deg_v\le \sqrt{M}, we use brute-force and the complexity is O(\deg_v^2)=O(\deg_v\sqrt{M});
- Otherwise \deg_v>\sqrt{M}, we enumerate all M edges and see if its two endpoints are both v's neighbors. This costs O(M)=O(\deg_v\sqrt{M}) time;
- The overall complexity is O(\sum_v\deg_v\sqrt{M})=O(M\sqrt{M}).

### Tester’s solution

When computing B(v), we enumerate v's neighbor w, and count the number of common neighbors of v and w. This can be done in O(\frac{N}{64}) by using bitsets: we maintain a huge binary number mask_v for every vertex v. mask_v's w-th bit is 1 if and only if (v,w)\in E. Then to count the number of common neighbors of v and w, we perform “and” operation on the two masks and count the number of 1's in the result, i.e, `(mask[v]&mask[w]).count()`

.

The overall complexity is O(\frac{MN}{64}).

### ALTERNATIVE SOLUTION:

If your solution is different with ours, feel free to leave a comment.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.