feruz.atamuradov's blog

Dp bitmask
By feruz.atamuradov, history, 6 years ago, In English

Hello codeforces community. can you help me problem on the dp.
task in russian

Consider an oriented graph G having n vertices numbered by positive integers from 1 to n. In the graph G, there may be several arcs between the same pair of vertices, as well as arcs leading from the vertex to it. Each arc of the graph is marked by some letter of the Latin alphabet. Each path in graph G can be put in correspondence with a string consisting of letters written on successively paths that pass through this path. This is the pathname of the path. We call the string S the path line of the graph G if there exists a path in it whose path label is S.

Your task is to calculate the remainder of dividing by 1 000 000 the number of waypoints of graph G consisting of exactly L symbols.

**Input**

The first line of the input data contains integers n, m, L (1 ≤ n ≤ 10, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 100) equal to the number of vertices and edges of the graph G, and also the length of the path lines that need to look for. The next m rows define the arcs of the graph G. Each of these lines contains two natural numbers a, b (1 ≤ a, b ≤ n) and a small Latin letter c, which means the presence of an arc from the vertex a to the vertex b marked with the symbol c. Elements of each line are separated from each other by spaces.

**Output**

The only output line must contain one number equal to the remainder of dividing the number of path lines of length L in column G by 1 000 000.

**Test**

4 4 100
1 2 a
2 3 b
3 4 a
4 1 b
ans : 2
  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

First of all, instead of constructing the actual graph, lets create a matrix next_nodes[A][B], storing for each node A, using the edges with symbol B, which nodes are possible to reach (mask).

Now, let DP[len][mask] be the number of path lines, of length len, that can be formed using a path that starts in any of the nodes marked in mask.

Initialy, DP[0][i] = 1, for 0 < i < 2^n. Then, DP[i][j] will be calculated this way:

For each lowercase letter c, compute next_mask, that represents the nodes reachable from mask j, using edges with that letter. In other words, next_mask is equal to the bitwise or of all next_nodes[node][c], if node is part of mask j. Finally, if next_mask != 0, add DP[i-1][next_mask] to DP[i][j].

Answer will be at DP[L][2^n-1].

→ Reply