DMOPC '14 Contest 6 P5 - Planning

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 0.6s
Memory limit: 64M
Author:
FatalEagle
Problem type

After hearing all the wonderful things about the TTC subway, you are finally splurging $11.50 (that's an hour's pay!) on a day pass so you can spend your beautiful sunny Saturday "Riding the Rocket" in dark tunnels. This calls for some planning!

You have a map, which looks like four equilateral "triangles" glued together (you're terrible at drawing triangles, so you draw squares that look like a triangle when glued together instead).

Your map ends up looking like something below (the triangles have "side length" 3 in this case).

With this map, you have effectively divided Toronto into square-shaped sectors! You know the subway system of Toronto has two very special properties — all subway lines cross exactly one edge between two square-shaped sectors! Also, each sector belongs to exactly one subway line. Therefore, there are two sectors joined by an edge in a single subway line.

You don't know the exact layout of the subway lines, and you're too lazy to go online and search it up. Therefore, you have adopted the foolproof strategy of drawing out all possible subway configurations for a map made up of equilateral triangles of side length N. Two configurations are different if any two sectors are joined by a subway line in one configuration, but they are not in the other. How many configurations do you have to draw? Since this number may be very large, output it modulo 998\,244\,353 (7 \times 17 \times 2^{23} + 1, a prime number).

Constraints

Subtask 1 [30%]

1 \le N \le 4

Subtask 2 [70%]

1 \le N \le 10^5

Sample Input

1

Sample Output

2

Explanation of Output for Sample Input

The two possible subway configurations (subway lines numbered for your convenience, same number indicates part of the same line):

  1         1
1   2     2   1
  2         2

Comments


  • 0
    pyrexshorts  commented on April 7, 2015, 9:48 p.m.

    Why is

    2

    2 1

    1

    for the sample case not valid?


    • 0
      awaykened  commented on April 7, 2015, 9:55 p.m.

      because it's the same thing as the first in the sample output


  • 0
    lolzballs  commented on April 7, 2015, 9:41 p.m.

    Are subway lines allowed to stop without reaching the other end of the map?


    • 0
      FatalEagle  commented on April 7, 2015, 10:07 p.m.

      Subway lines only consist of two "adjacent" squares.


      • 0
        lolzballs  commented on April 7, 2015, 10:19 p.m.

        So you can't have them span >3 squares?


        • 0
          FatalEagle  commented on April 7, 2015, 10:25 p.m.

          Nope.


  • 0
    lolzballs  commented on April 7, 2015, 9:15 p.m.

    With this map, you have effectively divided Toronto into square-shaped sectors

    Are the sectors the big thing(approximation of a square), or the individual "pixels" of the triangles?


    • 0
      FatalEagle  commented on April 7, 2015, 9:16 p.m.

      The "pixels".