UnluckyNumber | Topcoder Archive

Problem Statement

You are given a simple undirected graph consisting of n vertices and m edges. The vertices are numbered 1, 2, ..., n. You are also given an unlucky number z.

We need to colour each vertex of the graph with one of k colours. The colours are numbered 1, 2, ..., k.

Let c[i] be the color assigned to vertex i. A coloring is valid if for each edge (i, j) the value c[i] + c[j] does not equal the unlucky number z.

Find the number of such colourings modulo 10⁹ + 7.

You are given:

The number of vertices and edges: n and m.
The number of colours and the unlucky number that should not be the sum of colours for any edge: k and z.
The list of edges: two int[]s x and y with m elements each. For each valid index i, there is an edge connecting x[i] and y[i].

Definition

Class:: UnluckyNumber
Method:: numberOfColourings
Parameters:: int, int, int, int, int[], int[]
Returns:: int
Method signature:: int numberOfColourings(int n, int m, int k, int z, int[] x, int[] y)
(be sure your method is public)

Constraints

1 <= n <= 18
0 <= m <= min(18, n*(n - 1)/2)
1 <= k <= 10^9
2 <= z <= 2*k
x and y will each contain m elements
1 <= x[i], y[i] <= n
There will be no self-loops and all edges will be distinct.

Examples

```
2
```
```
1
```
```
5
```
```
2
```
```
{1}
```
```
{2}
```
```
Returns: 24
```
The two vertices can be coloured with any of the colours {1, 2, 3, 4, 5} except for the case where both are coloured 1. Thus, there are 5*5 - 1 = 24 possible colourings.
```
5
```
```
0
```
```
5
```
```
2
```
```
{}
```
```
{}
```
```
Returns: 3125
```
The graph is not necessarily connected. This graph consists of five isolated vertices. Each can be colored independently of the others, so the answer is 5^5 = 3125.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.